python中的OrderedDict与Dict

Question

在Tim Peter's answer中“有什么理由不使用有序字典”，他说。

OrderedDict是dict的子类。 这并不是很慢，但至少加倍的内存超过使用一个普通的小块。

现在，在通过particular question时，我尝试了使用ipython进行一些示例检查，它们都与前面的推理相矛盾：

1. dict和OrderedDict都是相同大小的。
2. 在OrderedDict上操作比在dict上操作所花费的时间容易得多7-8倍(因此要慢得多)

有人能解释一下我的推理哪里出错了吗？

创建一个大的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

我认为大小的问题是由于Python2.x __sizeof__中没有定义任何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

这在Python3中似乎是固定的，在这里现在有一个定义良好的__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