python - 为什么 OrderedDict() 比 dict() 和 list() 慢 10 倍？

Question

只需运行下面的测试，就会发现填充 anOrderedDict()大约比填充 adict()或 a慢一个数量级list()。

为什么？

# list()
In [1]: timeit test_list()
1000 loops, best of 3: 298 us per loop

# dict()    
In [3]: timeit test_dict()
1000 loops, best of 3: 269 us per loop

# dict()    
In [3]: timeit test_ord_dict()                                                  
100 loops, best of 3: 1.77 ms per loop

和：

def test_ord_dict():
  a = OrderedDict()
  for el in xrange(1000):
    a[el] = np.random.randint(100)
  return a

def test_dict():
  a = dict()
  for el in xrange(1000):
    a[el] = np.random.randint(100)
  return a

def test_list():
  a = list()
  for el in xrange(1000):
    a.append(np.random.randint(100))
  return a

Answer 1

OrderedDict是用纯 Python 实现的，所以这里是源代码的相关部分：

def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link at the end of the linked list,
    # and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, key]
    return dict_setitem(self, key, value)

如果键不存在，您将创建一个新列表并从列表中访问两个项目，这会减慢速度。

Answer 2

两个原因：

1. 根据定义， anOrderedDict必须比 a 做更多的工作dict。

2. （更重要的是）OrderedDict是用 Python 编写的，而dict和list是用 C 编写的。