OrderedDict性能(与双队列相比)
我一直在尝试对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回答 1
Stack Overflow用户
发布于 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
复制相似问题