python-rbtree和内建dict的性能比较
python内建的dict（字典）类使用的是hash算法，因此它的key不是有序的。而C++中的std::map或std::set使用的是平衡二叉树（通常为红黑树），其key是有序的。在网上搜了搜，找到了一个用C和pyrex混合实现的红黑树模块，python-rbtree。
我编写了一个极简单的测试程序，在Solaris x86 + python 2.4.4平台上运行，分别使用dict和rbtree，插入两百万个记录（key是3个整型，value是1个整型，你大概猜到我在干什么了吧
）。且在dict插入完之后，调用dict.keys().sort()对其key进行排序（也就是快排）。比较的结果是，两种方法使用的内存相当（大概在200M左右）。但是hash算法的速度要快一倍以上。当记录个数增加到五百万个时，结果还是差不多──即内存使用相当，hash算法快一倍。
至少在这个数量级上，内建的dict性能更佳。我还尝试了另一个纯Python的红黑树实现--RBTree.py，结果令人失望，在记录个数比较多的情况下，似乎根本无法得到正确的结果。
结论，python中的dict是可信赖的！
我编写了一个极简单的测试程序，在Solaris x86 + python 2.4.4平台上运行，分别使用dict和rbtree，插入两百万个记录（key是3个整型，value是1个整型，你大概猜到我在干什么了吧
）。且在dict插入完之后，调用dict.keys().sort()对其key进行排序（也就是快排）。比较的结果是，两种方法使用的内存相当（大概在200M左右）。但是hash算法的速度要快一倍以上。当记录个数增加到五百万个时，结果还是差不多──即内存使用相当，hash算法快一倍。至少在这个数量级上，内建的dict性能更佳。我还尝试了另一个纯Python的红黑树实现--RBTree.py，结果令人失望，在记录个数比较多的情况下，似乎根本无法得到正确的结果。
结论，python中的dict是可信赖的！
Hi Yong,
How's your Imput Methods project coming along? Have you tried it on SXCE76? How's the performance (& more importantly, stability)? Look forward to trying it again. Thanks and Best Regards.
发表于 W. Wayne Liauh 在 2007年11月19日, 04:06 上午 CST #
Hi, Wayne, did you mean scim and its ime(s)? No, I did not test it on latest SXCE build. I will update the specs and patches for scim-1.4.7.
发表于 Yong Sun 在 2007年11月19日, 09:00 上午 CST #
对的，用纯python写的算法程序效率非常低，我曾写过一个模拟ip路由交换的，如果纯python，一天时间才能运行完，如果c/c++,半个小时搞定，效率差别不是一点点，通常用python做外围的事，c/c++做核心的，这样可以做到开发效率和运行效率的平衡
发表于 jumbon 在 2007年11月29日, 08:55 上午 CST #