小编Tyl*_*ler的帖子

我一直在尝试在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 …