python - Python 中的 OrderedDict 与字典

Question

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

OrderedDict is a subclass of dict.

It's not a lot slower, but at least doubles the memory over using a plain 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

我认为 size 的问题是因为 Python 2.X 中没有定义 __sizeof__ 方法 implementation of 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