Почему OrderedDict () примерно в 10 раз медленнее, чем dict () и list ()?

Просто запустите приведенные ниже тесты и обратите внимание, что заполнение 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

python python-2.x
person Amelio Vazquez-Reina    schedule 24.08.2013    source источник
comment
Если кто-то найдет этот вопрос и просто захочет иметь dict, сохраняющий порядок размещения, вам больше не нужно использовать OrderedDict. Начиная с Python 3.7, язык теперь требует, чтобы dicts сохраняли порядок вставки https://mail.python.org/pipermail/python-dev/2017-December/151283.html.   -  person user136036    schedule 31.12.2019
comment
Спасибо @ user136036 Верно. Время летит.   -  person Amelio Vazquez-Reina    schedule 31.12.2019

Ответы (2)


arrow_upward
7
arrow_downward

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)

Если ключ не существует, вы создадите новый список и получите доступ к двум элементам из списка, что замедлит работу.

person Blender    schedule 24.08.2013
comment
@ZeroPiraeus У многих несущественных типов есть реализация C тоже, например deque и defaultdict (чтобы оставаться в пределах collections). - person ; 25.08.2013
comment
Разница в скорости изменилась в python3, теперь OrderedDict работает немного медленнее - person leonprou; 15.01.2017

arrow_upward
5
arrow_downward

Две причины:

  1. OrderedDict по определению должен делать больше, чем dict.

  2. (что гораздо важнее) OrderedDict написан на Python, а dict и _ 5_ написаны на C.

person Zero Piraeus    schedule 24.08.2013
comment
Я не уверен насчет первого. Это, безусловно, обеспечивает дополнительную гарантию, но реализация, полностью ориентированная на эти гарантии, не должна приводить к значительной дополнительной работе (см. Также: поток python-dev или python-ideas несколько месяцев назад об изменении в dict, которое автоматически сохранит порядок во многих случаях и облегчить обслуживание в других). Уж точно не хватило, чтобы быть на порядок медленнее. - person ; 25.08.2013
comment
@delnan Я согласен, что №2 намного важнее №1. Я не изучал код для OrderedDict, но не удивлюсь, если он будет более осторожным, чтобы быть как можно ближе к dict по поведению, чем с точки зрения производительности; по крайней мере, это был бы типичный подход в Python. - person Zero Piraeus; 25.08.2013