Python中的OrderedDict与Dict比较

Question

在Tim Peter对“有没有理由不使用有序字典”的回答中，他提到：

OrderedDict是dict的一个子类。

它的速度并没有慢很多，但使用它的内存大约是普通dict的两倍。

现在，在查看一个特定问题时，我用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

我觉得这个大小的问题是因为在Python 2.X中，OrderedDict没有定义__sizeof__这个方法，所以它就只能使用字典的__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中运行的，而列表的方法是在纯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