OrderedDict性能(与双端队列相比)

问题描述

我一直在尝试对Python中的BFS实现进行性能优化，而我最初的实现是使用双端队列来存储要扩展的节点队列和一个字典来存储相同的节点，这样我就可以高效地查找它是否已经打开.

I've been trying to performance optimize a BFS implementation in Python and my original implementation was using deque to store the queue of nodes to expand and a dict to store the same nodes so that I would have efficient lookup to see if it is already open.

我试图通过移至OrderedDict来优化(简单性和效率).但是，这会花费更多时间.完成400次样本搜索需要2秒钟的deque/dict和3.5秒的OrderedDict.

I attempted to optimize (simplicity and efficiency) by moving to an OrderedDict. However, this takes significantly more time. 400 sample searches done take 2 seconds with deque/dict and 3.5 seconds with just an OrderedDict.

我的问题是，如果OrderedDict的功能与两个原始数据结构相同，那么它的性能至少不应该相似吗?还是我在这里想念什么?下面的代码示例.

My question is, if OrderedDict does the same functionality as the two original data structures, should it not at least be similar in performance? Or am I missing something here? Code examples below.

仅使用OrderedDict:

Using just an 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

同时使用双端队列和字典:

Using both a deque and a dictionary:

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

推荐答案

deque 和 dict 均在C语言中实现，并且运行速度比 OrderedDict em>在纯Python中实现.

Both deque and dict are implemented in C and will run faster than OrderedDict which is implemented in pure Python.

OrderedDict 的优点在于，它像常规字典一样具有O(1)getitem，setitem和delitem.这意味着，尽管纯python实现较慢，它也可以很好地扩展.

The advantage of the OrderedDict is that it has O(1) getitem, setitem, and delitem just like regular dicts. This means that it scales very well, despite the slower pure python implementation.

使用双端队列，列表或二叉树的竞争性实现通常在其中一个类别中放弃快速的大Oh时间，以便在另一个类别中获得速度或空间上的好处.

Competing implementations using deques, lists, or binary trees usually forgo fast big-Oh times in one of those categories in order to get a speed or space benefit in another category.

更新:从Python 3.5开始， OrderedDict()现在具有C实现.尽管它还没有像其他一些容器那样经过高度优化.它应该比纯python实现快得多.然后从Python 3.6开始，已经对常规词典进行了排序(尽管尚不能保证排序行为).那些应该跑得更快:-)

Update: Starting with Python 3.5, OrderedDict() now has a C implementation. And though it hasn't been highly optimized like some of the other containers. It should run much faster than the pure python implementation. Then starting with Python 3.6, regular dictionaries has been ordered (though the ordering behavior is not yet guaranteed). Those should run faster still :-)

这篇关于OrderedDict性能(与双端队列相比)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！