python - 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

同时使用双端队列和字典:

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 实现的 OrderedDict 快。

OrderedDict 的优点是它具有 O(1) 的 getitem、setitem 和 delitem，就像常规的 dicts 一样。这意味着它可以很好地扩展，尽管纯 python 实现速度较慢。

使用双端队列、列表或二叉树的竞争实现通常会在其中一个类别中放弃快速的 big-Oh 时间，以便在另一个类别中获得速度或空间优势。

更新:从 Python 3.5 开始，OrderedDict() 现在具有 C 实现。尽管它没有像其他一些容器那样经过高度优化。它的运行速度应该比纯 python 实现快很多。然后从 Python 3.6 开始，对常规字典进行了排序(尽管还不能保证排序行为)。那些应该跑得更快:-)