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

Я пытался оптимизировать реализацию 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

Использование как deque, так и словаря:

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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