Можно ли ускорить этот поиск вширь?

У меня есть набор данных, который представляет собой большой невзвешенный циклический граф циклы происходят в циклах около 5-6 путей. Он состоит примерно из 8000 узлов, и каждый узел имеет от 1-6 (обычно около 4-5) соединений. Я выполняю вычисления кратчайшего пути одной пары и реализовал следующий код для выполнения поиска по ширине.

from Queue import Queue

q = Queue()
parent = {}
fromNode = 'E1123'
toNode = 'A3455'

# path finding
q.put(fromNode)
parent[fromNode] = 'Root'

while not q.empty():
  # get the next node and add its neighbours to queue
  current = q.get()
  for i in getNeighbours(current):
    # note parent and only continue if not already visited
    if i[0] not in parent:
      parent[i[0]] = current
      q.put(i[0])

  # check if destination
  if current == toNode:
    print 'arrived at', toNode
    break

Приведенный выше код использует модуль очереди Python 2.6, а getNeighbours () - это просто подпрограмма, которая выполняет один вызов MySQL и возвращает соседей в виде список кортежей, например (('foo',), ('bar',)). Вызов SQL выполняется быстро.

Код работает нормально, однако тестирование до глубины около 7 слоев занимает около 20 секунд для запуска (2,5 ГГц Intel 4GB RAM OS X 10.6)

Я приветствую любые комментарии о том, как улучшить время выполнения этого кода.

4 5
python algorithm computer-science breadth-first-search

4 ответа:

Ну, учитывая апвоты на комментарий, Я сделаю это ответом сейчас.

SQL в узком циклеопределенно замедляет вас. Мне все равно, как быстро он звонит. Подумайте об этом-вы просите, чтобы запрос был проанализирован, поиск был запущен-как бы быстро это ни было, он все еще находится в узком цикле. Как выглядит ваш набор данных? Можете ли вы просто SELECT поместить весь набор данных в память или, по крайней мере, работать с ним вне MySQL?

Если вы работаете с этими данными в памяти, вы увидите значительный прирост производительности.

11

Что-то вроде этого: 

#!/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-запросы словарем списков (а это будет сложнее всего), вы получите такую производительность.

1

Держу пари, что у этой машины больше одного ядра, не так ли? Запускайте его параллельно.

Python Threading

0

Хм, разве BFS не включает в себя маркировку узлов, которые вы уже видели, чтобы вы не посещали их снова?

0