Этот поиск в ширину может быть сделан быстрее?
Сборка "мусора" быстрее (больше эффективного времени), чем подсчет ссылок, если у Вас есть достаточно памяти. Например, gc копирования пересекает "живые" объекты и копирует их в новое пространство и может исправить все "мертвые" объекты за один шаг путем маркировки целого региона памяти. Это очень эффективно, , если у Вас есть достаточно памяти. Наборы поколений используют знание, что "большинство объектов умирает молодое"; часто только несколько процентов объектов должны быть скопированы.
[Это - также причина, почему gc может быть быстрее, чем malloc/free]
, Подсчет ссылок является намного большим количеством пространства, эффективного, чем сборка "мусора", так как это исправляет память самый момент, это становится недостижимым. Это хорошо, когда Вы хотите присоединить финализаторы к объектам (например, закрыть файл, как только объект Файла становится недостижимым). Система подсчета ссылок может работать, даже когда только несколько процентов памяти свободны. Но стоимость управления необходимости увеличить и постепенно уменьшить счетчики на каждое присвоение указателя стоила большого количества времени, и некоторая сборка "мусора" все еще необходима для исправления циклов.
, Таким образом, компромисс ясен: если необходимо работать в ограниченной памятью среде, или если Вам нужны точные финализаторы, используйте подсчет ссылок. Если Вы имеете достаточно памяти и нуждаетесь в скорости, используйте сборку "мусора".
4 ответа
Что ж, учитывая положительные голоса за комментарий, я дам ответ сейчас.
SQL в жестком цикле определенно замедляет вас. Меня не волнует, как быстро будет звонок. Подумайте об этом - вы просите, чтобы запрос был проанализирован, поиск был запущен - как бы быстро это ни было, это все еще в замкнутом цикле. Как выглядит ваш набор данных? Можете ли вы просто ВЫБРАТЬ весь набор данных в памяти или хотя бы работать с ним вне MySQL?
Если вы будете работать с этими данными в памяти, вы увидите значительный прирост производительности.
Могу поспорить, что у этой машины более одного ядра, не так ли? Запустите его параллельно.
Хм, разве BFS не помечает узлы, которые вы уже видели, чтобы вы не посещали их снова?
Примерно так:
#!/usr/bin/env python
from Queue import Queue
def traverse_path(fromNode, toNode, nodes):
def getNeighbours(current, nodes):
return nodes[current] if current in nodes else []
def make_path(toNode, graph):
result = []
while 'Root' != toNode:
result.append(toNode)
toNode = graph[toNode]
result.reverse()
return result
q = Queue()
q.put(fromNode)
graph = {fromNode: 'Root'}
while not q.empty():
# get the next node and add its neighbours to queue
current = q.get()
for neighbor in getNeighbours(current, nodes):
# use neighbor only continue if not already visited
if neighbor not in graph:
graph[neighbor] = current
q.put(neighbor)
# check if destination
if current == toNode:
return make_path(toNode, graph)
return []
if __name__ == '__main__':
nodes = {
'E1123': ['D111', 'D222', 'D333', 'D444'],
'D111': ['C01', 'C02', 'C04'],
'D222': ['C11', 'C03', 'C05'],
'D333': ['C01'],
'C02': ['B1'],
'B1': ['A3455']
}
result = traverse_path('E1123', 'A3455', nodes)
print result
['E1123', 'D111', 'C02', 'B1', 'A3455']
Если вы замените свои SQL-запросы словарем списков (а это будет сложная часть), вы получите такую производительность.