PyDict_MINSIZE
)开始;
2. 50,000个或更少条目的字典增长时会增加4倍;
3. 具有50,000个以上条目的字典增长时会增加两倍;
4. 键哈希值被缓存在字典中,因此在调整字典大小时不会重新计算。因此,如果您的字典有1,000,000个条目,我相信它将被调整大小11次(8→32→128→512→2048→8192→32768→131072→262144→524288→1048576→2097152),在调整大小期间需要进行2,009,768次额外插入。这似乎比将1,000,000个元素插入AVL树中所涉及的所有重新平衡的成本要小得多。
项目与独特项目的比例是多少? 预期有多少个独特项目?
如果哈希桶已满,则扩展只需要进行一些内存重新分配,而不是重新哈希。
测试计数字典应该非常快且易于完成。
请注意,自Python 2.7以来提供了计数器类 http://docs.python.org/library/collections.html#counter-objects http://svn.python.org/view?view=rev&revision=68559
如果想要击败内置的数据结构,你需要在C中实现自己的数据结构。
此外,如果使用get
,可以避免两次查找现有元素而节省一些开销。如果使用Python 2.7+,也可以使用collections.Counter。
def increment(map, key):
map[key] = map.get(key,0)+1
from collections import Counter
- Matthieu M.