我一直在尝试对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
发布于 2011-11-18 09:35:23
正如Sven Marnach所说,OrderedDict
是用Python语言实现的,我想补充的是,它是使用dict
和list
实现的。
python中的dict
是以哈希表的形式实现的。我不确定deque
是如何实现的,但文档显示deque
针对快速添加或访问第一个/最后一个元素进行了优化,所以我猜deque
是以链表的形式实现的。
我认为当你在OrderedDict上做pop
时,Python会进行哈希表查找,这比直接指向末尾和第一个元素的链表要慢。与哈希表相比,在链表的末尾添加元素也更快。
所以,在您的示例中,OrderDict
速度较慢的主要原因是,访问链表中的最后一个元素比使用哈希表访问任何元素都要快。
我的想法是基于书“美丽的代码”中的信息,它描述了dict
背后的实现细节,但是我不知道list
和deque
背后的太多细节,这个答案只是我对事物如何工作的直觉,所以如果我错了,我真的应该为我不确定的事情投下反对票。为什么我会说一些我不确定的事情?-Because我想测试我的直觉:)
https://stackoverflow.com/questions/8176513
复制相似问题