Я пытался оптимизировать реализацию BFS в Python, и моя первоначальная реализация использовала deque для хранения очереди узлов для расширения и dict для хранения тех же узлов, чтобы я мог эффективно искать, уже открыт.
Я попытался оптимизировать (простоту и эффективность), перейдя к OrderedDict. Однако это занимает значительно больше времени. 400 выполненных поисковых запросов занимают 2 секунды с deque/dict и 3,5 секунды с помощью только OrderedDict.
Мой вопрос: если 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
Использование как deque, так и словаря:
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
