为什么OrderedDict()比dict()和list()慢大约10倍？

Question

只需运行下面的测试，就会发现填充OrderedDict()比填充dict()或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

- Amelio Vazquez-Reina

---

如果有人发现这个问题，只是想要一个保留插入顺序的字典 - 您不再需要使用OrderedDict。自从Python 3.7以来，该语言现在要求字典保留插入顺序 https://mail.python.org/pipermail/python-dev/2017-December/151283.html。 - user136036

感谢 @user136036。没错，时间过得真快。 - Amelio Vazquez-Reina

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)

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

- Blender

---

@ZeroPiraeus 许多非必要类型也有C实现，例如deque和defaultdict（保持在collections内）。 - user395760

Python3 中的速度差异有所改变，现在 OrderedDict 只是稍微慢一点。 - leonprou

Answer 2

两个原因：

1. 按定义，OrderedDict 比 dict 做更多的工作。

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

- Zero Piraeus

---

我对第一个不太确定。它确实提供了额外的保证，但是完全针对这些保证的实现不应该导致显着的额外工作量（另请参见：几个月前有关更改dict以自动保留顺序并使其在其他情况下更易于维护的python-dev或python-ideas线程）。肯定不足以使速度慢一个数量级。 - user395760

@delnan我同意#2比#1更重要。我没有研究过OrderedDict的代码，但如果它在行为上尽可能接近于dict而不是追求性能，那么这将是Python中典型的方法。 - Zero Piraeus