Производительность OrderedDict (по сравнению с deque)

Question

Я пытался оптимизировать производительность реализации BFS в Python, и моя первоначальная реализация использовала deque для хранения очереди узлов для расширения и dict для хранения тех же узлов, чтобы у меня был эффективный поиск, чтобы увидеть, если это уже открыт.

Я попытался оптимизировать (простота и эффективность), перейдя в OrderedDict. Однако это занимает значительно больше времени. Выполнение 400 выборочных поисков занимает 2 секунды с deque / dict и 3,5 секунды только с OrderedDict.

Мой вопрос: если OrderedDict выполняет те же функции, что и две исходные структуры данных, разве он не должен быть по крайней мере похожим по производительности? Или я что-то здесь упускаю? Примеры кода ниже.

Использование только OrderedDict:

open_nodes = OrderedDict()
closed_nodes = {}
current = Node(start_position, None, 0)
open_nodes[current.position] = current

while open_nodes:
  current = open_nodes.popitem(False)[1]
  closed_nodes[current.position] = (current)

  if goal(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_nodes[new_node.position] = new_node

Использование словаря и словаря:

open_queue = deque()
open_nodes = {}
closed_nodes = {}
current = Node(start_position, None, 0)
open_queue.append(current)
open_nodes[current.position] = current

while open_queue:
  current = open_queue.popleft()
  del open_nodes[current.position]
  closed_nodes[current.position] = (current)

  if goal_function(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_queue.append(new_node)
    open_nodes[new_node.position] = new_node

Answer 1

Оба deque и dict реализованы на C и будут работать быстрее, чем OrderedDict , который реализован на чистом Python.

Преимущество OrderedDict заключается в том, что он имеет O (1) getitem, setitem и delitem, как обычные диктовки. Это означает, что он очень хорошо масштабируется, несмотря на более медленную реализацию чистого Python.

Конкурирующие реализации, использующие запросы, списки или двоичные деревья, обычно отказываются от быстрых больших раз в одной из этих категорий, чтобы получить преимущество в скорости или пространстве в другой категории.

Обновление: Начиная с Python 3.5, OrderedDict () теперь имеет реализацию на языке C. И хотя он не был сильно оптимизирован, как некоторые другие контейнеры. Он должен работать на намного быстрее, чем реализация на чистом Python. Затем, начиная с Python 3.6, были упорядочены обычные словари (хотя поведение упорядочения еще не гарантировано). Те должны бежать еще быстрее: -)

Answer 2

Как сказал Свен Марнах, в Python реализовано OrderedDict, я хочу добавить, что оно реализовано с использованием dict и list.

dict в python реализован как хеш-таблица. Я не уверен, как реализован deque, но в документации сказано, что deque оптимизирован для быстрого добавления или доступа к первым / последним элементам, поэтому я предполагаю, что deque реализован как связанный список.

Я думаю, что когда вы делаете pop в OrderedDict, python выполняет поиск по хеш-таблице, который медленнее по сравнению со связанным списком, который имеет прямые указатели на последний и первый элементы. Добавление элемента в конец связанного списка также быстрее по сравнению с хеш-таблицей.

Итак, основная причина, по которой OrderDict в вашем примере медленнее, заключается в том, что он быстрее обращается к последнему элементу из связанного списка, чем к любому элементу с использованием хэш-таблицы.

Мои мысли основаны на информации из книги Beautiful Code, она описывает детали реализации за dict, однако я не знаю подробностей за list и deque, этот ответ - просто моя интуиция о том, как все работает, так что в случае, если я ошибаюсь, я действительно заслуживаю отрицательных голосов за разговоры, в которых я не уверен. Почему я говорю вещи, в которых я не уверен? -Потому что я хочу проверить свою интуицию:)