OrderedDict性能（与deque相比）

Question

我一直试图在Python中对BFS实现进行性能优化，而我最初的实现是使用deque来存储要扩展的节点队列，使用dict来存储相同的节点，这样我就可以高效地查找它是否已经打开。

我试图通过移动到OrderedDict来优化（简单性和效率）。然而，这需要更多的时间。使用deque/dict完成400个样本搜索需要2秒，使用OrderedDict完成3.5秒。

我的问题是，如果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

Answer 1

deque和dict都是用C实现的，运行速度将快于纯Python实现的orderedict。

OrderedDict的优点是它有O（1）getitem、setitem和delitem，就像普通的dict一样。这意味着尽管纯python实现速度较慢，但它的伸缩性非常好。

使用deques、list或二进制树的竞争实现通常会放弃其中一个类别中的快速大Oh时间，以便在另一个类别中获得速度或空间效益。

更新：从Python 3.5开始，orderedict（）现在有一个C实现。尽管它没有像其他一些容器那样进行高度优化。它的运行速度应该比纯python实现快得多。然后从Python3.6开始，对常规字典进行了排序（尽管排序行为还没有得到保证）。它们应该跑得更快一些：-）

Answer 2

正如Sven Marnach所说，OrderedDict是用Python实现的，我想补充一下，它是用dict和list实现的。

python中的dict实现为哈希表。我不确定deque是如何实现的，但是文档中说deque是为了快速添加或访问第一个/最后一个元素而优化的，所以我猜deque是作为链表实现的。

我认为当您在OrderedDict上执行pop操作时，python执行哈希表查找，这比链接列表（它具有指向最后和第一个元素的直接指针）要慢。与哈希表相比，将元素添加到链表末尾的速度也更快。

因此，示例中OrderDict较慢的主要原因是，从链表访问最后一个元素比使用哈希表访问任何元素都快。

我的想法是基于《美丽的代码》一书中的信息，它描述了dict背后的实现细节，但是我不知道list和deque背后的很多细节，这个答案只是我对事情如何工作的直觉，所以如果我错了，我真的应该为我不确定的事情投票。为什么我要谈论我不确定的事情？-因为我想测试我的直觉：）