OrderedDict与Python中的Dict

Question

在蒂姆彼得的答案中,"有没有理由不使用有序词典",他说

OrderedDict是dict的子类.

它的速度并不慢很多,但至少使用普通字典使内存翻倍.

现在,在经历一个特定的问题时,我尝试了一些样本检查,ipython并且两者都与之前的推理相矛盾:

1. 既dict与OrderedDict相同尺寸的
2. 上的操作OrderedDict周围7-8倍更多的时间花费容易不是在操作dict(因此慢了很多)

有人可以向我解释我在推理中出错的地方吗？

---

创建一个大型Dict和OrderedDict并比较大小:

import sys
import random
from collections import OrderedDict

test_dict = {}
test_ordered_dict = OrderedDict()

for key in range(10000):
    test_dict[key] = random.random()
    test_ordered_dict[key] = random.random()

sys.getsizeof(test_dict)
786712

sys.getsizeof(test_ordered_dict)
786712

使用以下方法检查插入所用的时间%timeit:

import sys
import random
from collections import OrderedDict

def operate_on_dict(r):
    test_dict = {}
    for key in range(r):
        test_dict[key] = random.random()

def operate_on_ordered_dict(r):
    test_ordered_dict = OrderedDict()
    for key in range(r):
        test_ordered_dict[key] = random.random()

%timeit for x in range(100): operate_on_ordered_dict(100)
100 loops, best of 3: 9.24 ms per loop

%timeit for x in range(100): operate_on_dict(100)
1000 loops, best of 3: 1.23 ms per loop

Answer 1

我认为大小的问题是由于__sizeof__Python 2.X 实现中OrderedDict没有定义方法的事实,所以它只是回到dict的__sizeof__方法.

为了证明这一点,我在这里创建了一个A扩展的类,list并添加了一个额外的方法foo来检查是否会影响大小.

class A(list):
    def __getitem__(self, k):
        return list.__getitem__(self, k)
    def foo(self):
        print 'abcde'

>>> a = A(range(1000))
>>> b = list(range(1000))

但仍然返回相同的大小sys.getsizeof:

>>> sys.getsizeof(a), sys.getsizeof(b)
(9120, 9120)

当然A会变慢,因为它的方法在Python中运行而list的方法将在纯C中运行.

>>> %%timeit
... for _ in xrange(1000):
...     a[_]
... 
1000 loops, best of 3: 449 µs per loop
>>> %%timeit
for _ in xrange(1000):
    b[_]
... 
10000 loops, best of 3: 52 µs per loop

这似乎是在Python 3中修复的,__sizeof__现在有一个定义良好的方法:

def __sizeof__(self):
    sizeof = _sys.getsizeof
    n = len(self) + 1                       # number of links including root
    size = sizeof(self.__dict__)            # instance dictionary
    size += sizeof(self.__map) * 2          # internal dict and inherited dict
    size += sizeof(self.__hardroot) * n     # link objects
    size += sizeof(self.__root) * n         # proxy objects
    return size