Python中的OrderedDict与Dict有什么区别？

Question

在Tim Peter's answer回答“有没有不使用有序字典的理由”时，他说：

OrderedDict是dict的一个子类。

它的速度并没有慢多少，但使用它至少会使内存增加一倍。

现在，在查看particular question时，我尝试使用ipython进行了一些样本检查，其中两个与先前的推理相矛盾：

1. dict和OrderedDict的大小相同
2. 对OrderedDict进行操作需要比对dict进行操作花费更长的时间（因此速度更慢）

有人能解释一下我推理的错误之处吗？

---

创建一个大的字典和有序字典，并比较它们的大小：

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

- Anshul Goyal

Answer 1

我认为大小的问题是因为在 Python 2.X 的 OrderedDict 实现中没有定义__sizeof__方法，所以它会简单地回退到字典(dict)的__sizeof__方法。

为了证明这一点, 我在这里创建了一个继承自list的类A，并添加了一个额外的方法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 中，而列表的方法将运行在纯 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

- Ashwini Chaudhary

---

+1 我认为你对于缺少 __sizeof__ 的说法是正确的，但你的回答并没有解释 Tim 的观点，即 它不会慢很多。顺便说一下，无论我选择 100 个还是 10000 个键的范围，我得到的运行时间因子都是相同的 7-8 倍。 - Anshul Goyal

@mu無，也许这就是Tim所说的“很多”的意思。 - Ashwini Chaudhary

@mu無最好在他的回答下留言。 - Ashwini Chaudhary

Done - Anshul Goyal

还添加了一个额外的方法foo来检查它是否影响大小。添加方法不会增加实例的大小，因为方法是类上的属性。更准确的解释是，在子类的__init__中添加一个新属性“foo”。 - pankaj