Garey's Blog–FreeBSD/PHP/GoLang

二月 21st, 2010

[转]python-rbtree和内建dict的性能比较

6,791 views, Python, by garey.

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

 

原文:http://blogs.sun.com/yongsun/entry/python_rbtree%E5%92%8C%E5%86%85%E5%BB%BAdict%E7%9A%84%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83

Back Top

发表评论