OrderedDict性能（与deque比较）

Question

我一直在尝试优化我在Python中实现的广度优先搜索（BFS），最开始我用的是deque（双端队列）来存储要扩展的节点队列，同时用一个字典来存储这些节点，这样可以快速查找节点是否已经被打开。

为了提高效率和简单性，我尝试改用OrderedDict（有序字典）。但是，这样反而花费了更多的时间。用deque和字典进行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

正如Sven Marnach所说，OrderedDict在Python中是有实现的，我想补充一下，它是通过dict和list来实现的。

在Python中，dict是用哈希表来实现的。我不太确定deque是怎么实现的，但文档上说deque是为了快速添加或访问第一个和最后一个元素而优化的，所以我猜deque可能是用链表来实现的。

我认为，当你在OrderedDict上使用pop时，Python会进行哈希表查找，这比链表直接指向最后和第一个元素要慢。将一个元素添加到链表的末尾也比在哈希表中要快。

所以在你的例子中，OrderedDict比较慢的主要原因是，从链表中访问最后一个元素比通过哈希表访问任何元素要快。

我的想法是基于《美丽的代码》这本书中的信息，它描述了dict背后的实现细节，不过我对list和deque的具体细节了解不多，这个回答只是我对事情运作方式的直觉，所以如果我说错了，我真的应该被投反对票，因为我在说一些我不确定的事情。为什么我会说一些我不确定的事情呢？因为我想测试一下我的直觉 :)

Answer 2

首先，deque和dict这两个东西是用C语言写的，所以它们的运行速度比用纯Python写的OrderedDict要快。

OrderedDict的一个好处是，它在获取、设置和删除数据时，速度都是O(1)，这和普通的字典一样。这意味着即使它是用纯Python实现的，性能也很不错，能够处理大量数据。

其他一些实现方式，比如使用双端队列（deques）、列表（lists）或二叉树（binary trees），通常会在某些操作的速度上做出妥协，以便在其他方面获得更快的速度或节省空间。

更新： 从Python 3.5开始，OrderedDict()也有了C语言的实现。虽然它的优化程度没有其他一些容器高，但它的运行速度应该比纯Python的实现快得多。再往后，Python 3.6开始，普通字典也变得有序了（不过这种有序性还没有完全保证）。这些字典的运行速度应该会更快哦 :-)