OrderedDict性能(与deque相比)

Question

我一直在尝试在Python中性能优化BFS实现,我的原始实现是使用deque来存储节点队列以进行扩展,使用dict来存储相同的节点,这样我就可以有效地查找它是否已经打开.

我尝试通过移动到OrderedDict来优化(简单性和效率).但是,这需要更多的时间.完成400次样本搜索,使用deque/dict需要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

两个双端队列和字典是用C语言实现,并且将运行速度比OrderedDict其在纯Python实现.

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

使用deques,list或binary tree的竞争实现通常会在其中一个类别中放弃快速的大哦时间,以便在另一个类别中获得速度或空间优势.

更新: 从Python 3.5开始,OrderedDict()现在有一个C实现.虽然它没有像其他一些容器那样高度优化.它应该比纯python实现运行得快得多.然后从Python 3.6开始,已经订购了常规字典(虽然订购行为尚未得到保证).那些应该跑得更快:-)