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是可信赖的!

3 thoughts on “python-rbtree和内建dict的性能比较

  1. 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.

  2. 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.

  3. 对的,用纯python写的算法程序效率非常低,我曾写过一个模拟ip路由交换的,如果纯python,一天时间才能运行完,如果c/c++,半个小时搞定,效率差别不是一点点,通常用python做外围的事,c/c++做核心的,这样可以做到开发效率和运行效率的平衡

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha