Shell's Home

Nov 28, 2011 - 1 minute read - Comments

python中dict的插入复杂度估算和排重复杂度估算

在做分词核心词典数据结构分析的时候需要,就先写一篇吧。

具体可以参考python源码解析读书笔记(一)——内置对象,这里面有说:

7.dict对象的索引方案

dict对象的索引方案使用的是哈希表,而且是开放地址法的哈希表。当装载率达到一定规模后,会新申请一块内存,将有效数据复制过去。最小的表空间为8个对象,当装载率超过2/3时,会扩大规模到当前active的4倍(超过50000个对象为2倍)。目前为止,在对象被删除后,其表空间并不释放。因此曾经增长的非常大的dict对象,可以定期复制以回收空间。

最初的表项空间为6个以内,满了之后,会自动扩张到24个,有效16个。从大致来说,如果要放下N个表项,大概就要扩张T次,他们满足以下关系。

A0*(8/3)^(T-1)<N<A0*(8/3)^T

而每次扩张,就要进行全表项复制,因此复杂度大约是O(N)量级。当扩张到放下N个表项时,就需要进行的复制的总数是:

sum(i, 0, T-1){A0*(8/3)^i}

这是一个典型的等比数列求和问题,我们知道问题的答案应当是:

A0*3*((8/3)^T-1)/5=A0*(3/5)*(8/3)^T-(3/5)*A0

因此,(3/5)(N-A0)<O<(3/5)\*((8/3)\*N-A0)。如果只考虑数量级的话,插入的复杂度量级为O(n),即哈希表的平均插入复杂度为n级。

也许有人奇怪,哈希表的插入复杂度为1级阿,怎么得到n级的结论的?看上面,都说是放下N个表项时的总复杂度了。

我们可以和红黑树对比一下,红黑树的平均插入复杂度为logn级,平均查找复杂度为logn级。哈希表的平均插入复杂度为1级,查找复杂度为1级。但是红黑树在一点上比hash优秀——他的插入时间基本稳定,hash table的插入时间有可能会暴长。

于是,当我们有N个元素,需要进行排重的时候,我们可以set化。假定set和dict基于一样原理运作,我们的时间复杂度为O(n+m)级,m为排重后元素个数。其实按照最差情况来说,也可以认为是O(n)级。