Оптимизация алгоритма всех путей

Question

Я успешно использовал следующий алгоритм, чтобы завершить все пути до длины пути 10 на графиках ~900 узлов. Тем не менее, я хочу увеличить масштаб до больших графиков, и мне интересно, есть ли дальнейшая оптимизация, которую я могу сделать. Пока что у меня есть:

• После того, как узел завершил свою DFS, пути сохраняются в хеш-таблицу. Если указанный узел встречается, к нему добавляются пути из хеш-таблицы, поэтому работа не повторяется.
• Узлы отсортированы по степени (по возрастанию). Таким образом, наиболее вероятные узлы уже будут в хеш-таблице.

Специфика алгоритма: строит сеть из химических веществ (узлов) и реакций (ребер) и создает пути, чтобы впоследствии их можно было искать намного быстрее для теоретических путей, которые впоследствии можно будет проверить экспериментально.

Алгоритм основан на сети x all_simple_paths алгоритм:

def _all_simple_paths_graph(DG, cutoff):
    memorizedPaths = {}
    nlist = []
    #sorts nodes into highest -> lowest degree order
    degreelist = sorted(DG.degree_iter(),key=itemgetter(1),reverse=True)
    for i in degreelist:
        t = re.findall("'\s*([^\"]*)\s*'",str(i))
        nlist.extend(t)
    with open ('PythonOutput.txt', "wb") as csvfile:
        writer = csv.writer(csvfile, delimiter=' ', quotechar='|')
        numberdone = 0
        #for each node start a new DFS
        for source in nlist:
            print source 
            print numberdone
            numberdone += 1
            uniqueTreePaths = []
            if cutoff < 1:
                return
            visited = [source]
            stack = [iter(DG[source])]
            while stack:
                children = stack[-1]
                child = next(children, None)
                if child is None:
                    stack.pop()
                    visited.pop()
                #If a node has been searched before, append its paths
                elif child in memorizedPaths:
                    for path in memorizedPaths[child]:
                        newPath = (tuple(visited) + tuple(path))
                        if (len(newPath) <= cutoff) and (len(set(visited) & set(path)) == 0):
                            uniqueTreePaths.append(newPath)
                    continue
                elif len(visited) < cutoff:
                    if child not in visited:
                        visited.append(child)
                        stack.append(iter(DG[child]))
                        if visited not in uniqueTreePaths:
                            uniqueTreePaths.append(tuple(visited))
                else: #len(visited) == cutoff:
                    if (visited not in uniqueTreePaths) and (child not in visited):
                        uniqueTreePaths.append(tuple(visited + [child]))
                    stack.pop()
                    visited.pop()
            #for each node, write to disk to save RAM
            for path in uniqueTreePaths:
                writer.writerow(path)
            #add paths for each node to the hash table
            memorizedPaths[source] = uniqueTreePaths

Если у кого-нибудь есть предложения по дальнейшей оптимизации алгоритма, это будет с благодарностью.

Answer 1

Прежде всего - измерение - ваш лучший друг. Если вы не собираете информацию о том, сколько времени занимает алгоритм, то у вас нет реального способа узнать, помогает ли изменение или нет. Ваша идея кэшировать свои результаты умна, но вы должны проверить время с и без кэширования, чтобы убедиться, что оно действительно помогает.

В частности, одна часть вашего кода, в которой я вижу возможности для улучшения, if (visited not in uniqueTreePaths)..., Вы проверяете, содержится ли список в списке списков. Я не уверен, что лучший способ исправить это (опять же, собрать данные синхронизации из вашего кода), но одна из возможностей - представить пути в виде строк, а не списков, позволяя хранить их с помощью хэшей.