自己山寨了一个红黑树，拿来和 Dictionary 作性能对比，结果发现速度慢很多（N < 1,000,000 时，接近一个数量级）。山寨的代码未经优化，和 BCL 里面的代码拼速度的确没啥意义。该红黑树的读写速度严格按照 Log(N) 退化，这说明我的实现和测试方法没有大的问题。而 Dictionary 虽然性能也在退化，但是却要平缓得多。红黑树唯一的优势是内存占用较低，基本上是 Dictionary 的一半。

    不过，从理论上很容易证明红黑树在性能上的劣势。红黑树是一个有序的结构，为了保持其有序的结构，自然需要付出更高的代价（从这个角度而言，红黑树和 Dictionary 的差别，正如基于 Heap 的 PriorityQueue 和 SortedList 的区别一样，前者只维护一个偏序）。Dictionary 中间的数据是无序的（因此 Hash 被某些人翻译成“杂凑”），如果不快一点实在对不起它消耗的内存（空间换速度）。此外，Dictionary 的性能与 hashcode 的质量有很大的关系，因此在存在 Hash Collision 的情况下性能会退化；Dictionary 不能像红黑树那样保证最坏情况下具有 log(N) 的性能，从而在更普遍的场合提供更高的性能和更好的 Scalability。

    其实，在大多数场合下，红黑树和 Dictionary 并不具备可比性——Dictionary 的应用场合要广很多。大概，这就是 .NET BCL 不提供红黑树（或者 AVL 树）的理由吧。更正：BCL 中的 TreeSet 就是一个非标准版本的红黑树，并且提供了 TreeDictionary 作为关联数组。神奇的是，在我的简单 Benchmark 下面，我的山寨版本读速度慢，写速度快，差距都低于 20%。至于内存占用，还是山寨版本用得少（因为简陋）。

    最后，再谈谈红黑树的一些鲜为人知的优点：红黑树可以通过 path copy 在操作时保留原有的树结构，其空间开销为 log(N)；红黑树可以通过 Sleator, Tarjan 的方法构造 persistent 版本，即保留所有历史版本，一次操作的空间开销仅为常数。而这些，都是 Dictionary 等基于 hash 的数据结构所不具备的优良特性。

    但是，在下面这篇文章中，作者认为 Java 的 TreeMap 和 HashMap 性能相当。这是否说明 CLR 的 Dictionary 要比 Java 的 HashMap 效率要高呢？我表示谨慎的怀疑。水木上的一位网友认为，这是测试者的使用不当，HashMap 的性能主要被 resize 所限制（相信很多人受过 StringA = StringA + StringB 的罪吧）。

性能比较

我们仍然比较Red-Black Tree同Hash table的性能区别。Red-Black Tree使用Java的TreeMap来实现；Hash Table使用HashMap来实现。

5千万数据, 每50个为一组，插入50个8位长的随机数，在达到30个之后再每次删除一个元素。

测试结果

HashMap 20秒

TreeMap 18秒

源文档 <http://hi.baidu.com/jabber/blog/item/46ddc3ef383cfa30acafd5c8.html>

    相信大家都知道设计模式中的 Iterator 和 Oberver，但是恐怕很少有人知道这两种模式在范畴论中是对偶关系（Duality）。想知道细节，请去 Channel 9 吧！

     All hail Category!

BTW: Erik 和 Brian 在解释 Contra-variant 的时候还是犯了点错误的，这些概念绕来绕去实在头痛。

     我常用的便携设备有四台，分别是 魅族 M8，汉王 N518，Fujitsu U1010 和 HP 2710p。我随身携带 M8，上班时携带 N518，周末出门携带 2710p，U1010 早已被束之高阁。这些设备无一例外的都是 Windows 设备，N518 使用的是 CE5，而 M8 使用的是 CE6。

    HP 2710p 的屏幕采用 LED 背光的亚光玻璃面板，在明亮的地方也可以阅读。这是我的设备里面唯一可以正常阅读各种论文的。其缺点是太重，不可能随身带着阅读，别说在地铁上，就是在沙发上捧着都累。2710p 的功耗控制得比较好，两颗电池足够我连续工作六到七小时，我很少携带电源出门。

    U1010 的阅读体验是最糟糕的，高光面板反光严重。虽然它只有 0.7kg，但我在地铁上用过一次，手腕很快就发酸了。它的 DPI 太高，用来读一般的网页实在是痛苦。U1010 的功耗虽然低，但是电池也不太强劲，加厚的四芯电池也仅够三小时上网。

    M8 的屏幕非常精细，反光也控制得不错，虽然不如 2710p，但在智能手机中也算是极品了。有人拿 M8 读电子觉得很好，但是我觉得它并不适合长时间阅读。它的优点是随时随地可以连接网络，阅读最新的 RSS 内容。最奇特的是，虽然大家都痛恨 M8 的 Opera，我却觉得 M8 阅读普通网页比 U1010 用户体验更好。M8 的耗电量很大，但是一个电池基本上能撑一天。

    N518 无疑提供了最佳的阅读体验。由于使用了 e-ink 技术，它适合长时间阅读。它仅比 M8 重一些，比我的大部分藏书都要轻，可以长期单手操作。它是这些设备中最省电的，我经常忘了关机，第二天依然电力十足。它是这些设备中唯一不能上网的，因而限制了其应用。如果 N518 可以通过蓝牙与其他 Windows 设备进行随时同步，那它将是一个完美的阅读设备。

    作为一个移动计算的狂热者，我一度热衷于平板电脑、UMPC、MID 这些概念，并且吃了不少螃蟹。我过去认为，用户对移动计算设备有多层次的需求，这个市场上将会有智能手机、手持设备、超便携笔记本、普通笔记本等多个细分市场。但通过我自己的亲身体验，我意识到根本没有什么中间路线，将来的移动计算设备将只有两条路线：随身携带的智能手机和高性能笔记本。

    没有任何设备可以取代高性能笔记本的地位。对于专业的 IT 从业者，只有高性能的笔记本能满足工作的需求。即便是对于摄影爱好者，U1010 这样的设备也无法胜任图片检阅和编辑功能。我尝试过用 U1010 进行文学创作，结果发现它完全不适于长时间的文本输入。至于一般的手持设备或智能手机，更是无法完成这样的任务。

    智能手机的功能变得越来越强大，手机上的 Opera Mobile、Chrome Lite、Safari 可以胜任大部分网页的浏览。越来越多的手机预装了 Google 的软件，可以处理邮件。智能手机的媒体播放能力也越来越强大，让功能单一的媒体播放器的生存空间越来越小。智能手机上的应用具有一个极大的优点，那就是随时随地都可以使用，并且从拿出设备到完成任务的时间间隔非常短。像 U1010 这样的设备则不具备这样的特性，因为它是按照桌面应用进行设计的。

    回顾过去一年多，我只有在没有主力的笔记本时，才会频繁使用 U1010。当我购入 2710p 之后，U1010 便束之高阁了。现在我又有了 M8，在床上看视频都用不着 U1010 了。现在 U1010 也就剩下一个无可替代的应用——如厕时上水木灌水。

    汉王 N518 买了一个月了，一直想写个评测，但是也没啥好说的——因为这事已经被人做了，而且做得比我好：

轩辕一笑的 N518 介绍

一路书香的 N518 评测

    既然好话都被人说了，我就挑点刺吧。首先，编辑没有 copy/paste，更没有 undo/redo，一旦操作失误或者误删了文档，麻烦就大了。其次，笔迹不能存储为图片，也没有配套的软件可以从 PC 读取；既然是 Windows CE 的内核，完全可以导出成 digital ink，在平板电脑上输出成矢量笔迹（Windows Journal 和 Onenote 还能进行文本识别）。最后应该提供第三方程序的接口，并提供相应的 SDK，这上面的日记软件和记账软件肯定很受欢迎。

    话又说回来，我买 N518 的初衷是用来书写而不是阅读的。N518 比平板电脑更适合随身携带，可以随时记笔记。这玩意儿最大的缺点是贵（虽然和 iRex Iliad 比起来，还是便宜不少），但如今全民保八，消费就是爱国。支持国货，从我做起！

    Windows Vista SP1/IE8/FlashGet 3.1

    FlashGet 的 BHO 拦截了浏览器的鼠标按键事件，在 DOM 很复杂的情况下会消耗大量的 CPU 资源，阻塞脚本运行。这个 BHO 的作者大脑可能严重积水，很可能会对 DOM 进行全遍历，包括不可见的页面元素。

    FlashGet BHO intercepts the mouse-click event, and consumes massive CPU resources when the DOM is complex. The author of this BHO may suffer from brain damage, since the hooked program seems to walk through the entire DOM including the hidden elements.

    M8 默认的字体虽然不错，但是和专为高 DPI 设备设计的微软雅黑比起来，还是差了不少。后面一个字体是雅黑，其特点是字比较大，线条更粗，更圆润。

警告：拆机会导致客服拒绝换机，要返厂检查，苦。

    我对 M8 的外观还算满意，但是很厌恶它那亮闪闪的外壳——整一个塑料质感十足的指纹收集器。今天去 Meizu 专卖店想买个薄点的套遮丑，结果发现居然有亚光的外壳卖，但是得自己动手换。这东西价钱还算厚道，连工具才 50 块钱。正好我去修 P1i，让奸商帮我拆掉原来的后盖（原厂的后盖实在是太结实了，我自己实在是拆不开），M8 立刻焕然一新，手感顿时好了很多。

    替换的外壳有几处细微的不同：音量孔变长了，耳机插孔变小了，话筒处由一个大孔变为三个小孔。虽然我认为替换的外壳的话筒设计更加漂亮，但是原厂的外壳加工精度更高一些，扣得也要严实一些。有一点是肯定的，自行更换外壳以后，换新机器至少要加 180 元了（据说单送原厂换壳就要 80 元）。因此，除非像我这样憎恶光面材料的偏执狂，还是不要更换外壳的好。

    考虑到这个世界上还是有很多吹毛求疵的人，还是有必要介绍一下更换外壳的流程：

 
打开后盖，卸掉电池和 SIM 卡，拆两颗螺钉

 
用工具或指甲撬开外壳（不要用改锥）

 
侧面的卡扣

头部的卡扣

    既然拆开了，插播 M8 的半裸照：

 
其实穿得挺多的

 
USB 小口的固定和屏蔽还不错

 
头部

 
摄像头和扬声器

    买来的替换外壳上是缺几个零件的，一定要从原厂的壳子上转移过来：

不知道有啥用的金属片

摄像头挡板

 
扬声器的防尘网，有两个

    我买来的这个外壳加工精度有点问题，USB 接口部门卡不紧（其实很细微）。

不到 0.5 mm 的偏差，但是我实在受不了

 
看来是模具不过关，误差比较大

 
关公刮骨疗伤，刮塑料小儿科

 
其实还是很麻烦

 
问题解决了

 
缝隙还是有的，不过这次正常多了

    最后是广告时间：有人要 P1i 和 U1010 么？

    花重金买了个电动牙刷（Philips HX6932/10），其中一半的价钱都花在 UV 消毒底座上了，结果说明书上一句“可以在每次使用杀菌器之后清洁牙刷头”让我百思不得其解。我到底是每天清洁呢，还是每周清洁？直到我找出英文版本的说明书，读到“With the sanitiser, you can clean your brush head after every use”，才明白，原来每次刷完牙都可以使用 UV 消毒。看来 Philips 根本没把中国市场的消费者当回事。希望电动牙刷市场也能有 Meizu 这样锐意进取的国产玩家，提供一些性价比高又贴近中国消费者的产品。

     P1i 的滚轮又坏了，我本来打算买个 N97 用上几年，结果鬼使神差地买了 M8。这玩意儿外表很光鲜，但是小毛病实在太多，可以说是罄竹难书，我就不再赘述了。我想说的是，即便需要忍受它的诸多毛病，我仍然被这部手机给迷住了，短时间内不再想要别的手机了。这不，不到一周我就把 P1i 的数据备份完毕，将它束之高阁了。

    M8 至今没有 1.0 的固件，并不是魅族的程序员太差，而是黄章的野心实在太大。我必须向黄章致以最高的敬意，魔鬼存在于细节之中：

按联系人整理的通话记录

一目了然的 Speed Dial（虽然我从来不用）

方便易用时钟和闹铃

实用的统计信息

简单易用的备份系统

    我没用过 iPhone，不知道这些是否是抄袭。

    大部分 M8 用户对它爱不释手的原因是屏幕，主要用 M8 来看视频和电子书。我也就用它看看 MSDN 上的视频，主要都用听的；我有汉王的 E-ink 产品，电子书这个功能对我来说完全是鸡肋。真正吸引我的还是 Opera，虽然有种种毛病，但是毕竟能无障碍地访问大多数网页。此外，它还是打发时间的利器，托 iPhone/iPod Touch 的福，M8 也可以在线观看视频（需要 WiFi）：