Оптимизация реализации алгоритма Дейкстры на Python

[kotenok gav]

Здравствуйте!
Было задание для графа записанного в текстовый файл в форме:
Первая строка: число вершин, пробел, число ребер
Остальные строки: номер одной вершины (номера начинаются с 1), пробел, номер второй вершины, пробел, вес ребра соединяющего эти вершины.

Потом после запуска программы вводятся номера начальной и конечной вершин, и программа с помощью алгоритма Дейкстры должна найти кратчайший путь между этими вершинами. Сделал программу:

Используется синтаксис Python

import networkx as nx
G=nx.Graph()
abc=open("d2103.eliminated.wel")
w=abc.readline()
o=w.split()
m=int(o[0])
n=int(o[1])
for i in range(n):
    t=abc.readline()
    r=t.split()
    x=int(r[0])
    y=int(r[1])
    z=int(r[2])
    G.add_edge(x, y, weight=z)
abc.close()
n=int(input())
k=int(input())
a=[[float('inf'), i+1] for i in range(m)]
a[n-1][0]=0
b=[]
for i in range(m):
    b.append([])
b[n-1]=[n]
c=[]
e=[i for i in range(1, m+1)]
while True:
    for i in range(len(e)):
        found = False
        if e[i] not in c:
            found=True
            break
    if not found:
        break
    f=[]
    for i in a:
        if i[1] not in c:
            f.append(i)
    g=[]
    for i in range(len(f)):
        g.append(f[i][0])
    v1=min(g)
    for i in f:
        if i[0]==v1:
            v=i[1]
            break
    c.append(v)
    for u in G[v]:
        if u not in c:
            if a[u-1][0]>a[v-1][0]+G[v][u]['weight']:
                a[u-1][0]=a[v-1][0]+G[v][u]['weight']
                b[u-1]=[]
                for i in range(len(b[v-1])):
                    b[u-1].append(b[v-1][i])
                b[u-1].append(u)
print(b[k-1])
 

Но эта программа работает намного медленее чем встроенный алгоритм Дейкстры (

Используется синтаксис Python

import networkx as nx
G=nx.Graph()
abc=open("d2103.eliminated.wel")
w=abc.readline()
o=w.split()
m=int(o[0])
n=int(o[1])
for i in range(n):
    t=abc.readline()
    r=t.split()
    x=int(r[0])
    y=int(r[1])
    z=int(r[2])
    G.add_edge(x, y, weight=z)
abc.close()
n=int(input())
k=int(input())
print(nx.dijkstra_path(G, n, k))

), три минуты против двух секунд. Почему у меня так медленно и как это исправить?

[Pphantom]

Вообще говоря, сам по себе Python - штука очень медленная. "Батарейки" для него очень часто представляют собой обертку для кода, написанного на существенно более высокопроизводительных языках (для этого пакета это тоже верно). Так что разница в скорости на два порядка сама по себе чем-то из ряда вон выхоядщим не является.

[kotenok gav]

Так алгоритм Дейкстры встроенный в networkx тоже на Python!

[Geen]

Ну, во-первых, если "встроенный" алгоритм "скомпилирован", то разница вполне ожидаема.

Но в Вашем варианте, например, вместо использования кучи, как я вижу, идёт постоянное создание/сканирование массивов...

[kotenok gav]

Geen в сообщении #1276496 писал(а):

кучи

Какой кучи?

[Geen]

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

-- 19.12.2017, 15:23 --

kotenok gav в сообщении #1276497 писал(а):

Geen в сообщении #1276496 писал(а):

кучи

Какой кучи?

https://ru.wikipedia.org/wiki/Куча_(структура_данных)

[mihaild]

Вообще при выкладывании кода лучше бы дать переменным понятные имена.

Оцените асимптотику вашей реализации (на первый взгляд очень похоже, что у вас тем лишняя степень по числу вершин затесалась).

Geen в сообщении #1276496 писал(а):

Ну, во-первых, если "встроенный" алгоритм "скомпилирован", то разница вполне ожидаема.

Если модуль написан на питоне (без бинарных вставок), то производительность не должна отличаться от использования такого же кода напрямую.

[slavav]

В вашем решении есть две проблемы.
1. Большие константы. Я имею ввиду что некоторые фрагменты написаны так что они выполняются медленнее (в константное число раз) чем их оптимальные варианты. Прежде всего это циклы вида

for i in range(len(array)):

. Их можно ускорить.
2. Алгоритмическое замедление. Некоторые операции имеют не оптимальную сложность. Вот этот и другие похожие куски можно существенно ускорить:

if i[1] not in c:

. Вы делаете поиск по массиву, что медленно. Его можно заменить на более быструю поисковую структуру.

Вам нужно повторить тему "контейнеры и сложность операций". И ещё раз перечитать описание алгоритма Дейкстры.

[kotenok gav]

Ой, один len совсем не нужен. Сейчас переделаю.

-- 19 дек 2017, 23:51 --

Исправленная программа:

Используется синтаксис Python

import networkx as nx
G=nx.Graph()
abc=open("d2103.eliminated.wel")
w=abc.readline()
o=w.split()
m=int(o[0])
n=int(o[1])
for i in range(n):
    t=abc.readline()
    r=t.split()
    x=int(r[0])
    y=int(r[1])
    z=int(r[2])
    G.add_edge(x, y, weight=z)
abc.close()
n=int(input())
k=int(input())
a=[[float('inf'), i+1] for i in range(m)]
a[n-1][0]=0
b=[]
for i in range(m):
    b.append([])
b[n-1]=[n]
c=[]
found = False
while True:
    for i in range(1, m+1):
        if i not in c:
            found=True
            break
    if not found:
        break
    f=[]
    for i in a:
        if i[1] not in c:
            f.append(i)
    g=[]
    for i in range(len(f)):
        g.append(f[i][0])
    v1=min(g)
    for i in f:
        if i[0]==v1:
            v=i[1]
            break
    c.append(v)
    for u in G[v]:
        if u not in c:
            if a[u-1][0]>a[v-1][0]+G[v][u]['weight']:
                a[u-1][0]=a[v-1][0]+G[v][u]['weight']
                b[u-1]=[]
                for i in range(len(b[v-1])):
                    b[u-1].append(b[v-1][i])
                b[u-1].append(u)
print(b[k-1])
 

Время увеличилось до практически 6 минут.

[kotenok gav]

Придумал еще одно исправление, сейчас пересчитаю.

-- 20 дек 2017, 01:05 --

Исправленная программа:

Используется синтаксис Python

import networkx as nx
G=nx.Graph()
abc=open("d2103.eliminated.wel")
w=abc.readline()
o=w.split()
m=int(o[0])
n=int(o[1])
for i in range(n):
    t=abc.readline()
    r=t.split()
    x=int(r[0])
    y=int(r[1])
    z=int(r[2])
    G.add_edge(x, y, weight=z)
abc.close()
n=int(input())
k=int(input())
a=[[float('inf'), i+1] for i in range(m)]
a[n-1][0]=0
b=[]
for i in range(m):
    b.append([])
b[n-1]=[n]
c=[]
found = False
while True:
    for i in range(1, m+1):
        if i not in c:
            found=True
            break
    if not found:
        break
    f=[]
    for i in a:
        if i[1] not in c:
            f.append(i)
    g=[]
    for i in range(len(f)):
        g.append(f[i][0])
    v1=min(g)
    for i in f:
        if i[0]==v1:
            v=i[1]
            break
    c.append(v)
    for u in G[v]:
        if u not in c:
            if a[u-1][0]>a[v-1][0]+G[v][u]['weight']:
                a[u-1][0]=a[v-1][0]+G[v][u]['weight']
                b[u-1]=[]
                for i in range(len(b[v-1])):
                    b[u-1].append(b[v-1][i])
                b[u-1].append(u)
print(b[k-1])
 

Время по-прежнему практически 6 минут.

[mihaild]

mihaild в сообщении #1276499 писал(а):

Оцените асимптотику вашей реализации

slavav в сообщении #1276500 писал(а):

И ещё раз перечитать описание алгоритма Дейкстры

[kotenok gav]

Может проблема в этом куске?:

Используется синтаксис Python

    f=[]
    for i in a:
        if i[1] not in c:
            f.append(i)
    g=[]
    for i in f:
        g.append(i[0])
    v1=min(g)
    for i in f:
        if i[0]==v1:
            v=i[1]
            break

Я делал этот кусок кода чтобы найти вершину, не в списке посещенных вершин (c), и с наименьшим текущим расстоянием от начальной вершины. Может, как-то можно заменить этот кусок кода?

-- 20 дек 2017, 15:38 --

mihaild в сообщении #1276499 писал(а):

Оцените асимптотику вашей реализации

А как это сделать?

[mihaild]

kotenok gav в сообщении #1276673 писал(а):

Может, как-то можно заменить этот кусок кода?

Посмотрите на структуру данных "куча" (heap). Ну или хотя бы храните текущее расстояние до каждой вершины в массиве, который обновляйте при добавлении новой вершины. Так, чтобы по каждому ребру "проходить" один раз, а не при добавлении каждой вершины.

kotenok gav в сообщении #1276673 писал(а):

А как это сделать?

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

[warlock66613]

mihaild в сообщении #1276680 писал(а):

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

Ещё надо учесть сложность используемых готовых функций и конструкций, таких как if i not in c.

[kotenok gav]

Переписал программу с использованием кучи:

Используется синтаксис Python

import networkx as nx
import heapq
G=nx.Graph()
abc=open("d2103.eliminated.wel")
w=abc.readline()
o=w.split()
m=int(o[0])
n=int(o[1])
for i in range(n):
    t=abc.readline()
    r=t.split()
    x=int(r[0])
    y=int(r[1])
    z=int(r[2])
    G.add_edge(x, y, weight=z)
abc.close()
n=int(input())
k=int(input())
a=[]
heapq.heappush(a, (0, n, [n]))
for i in range(1, n):
    heapq.heappush(a, (float('inf'), i, []))
for i in range(n+1, m+1):
    heapq.heappush(a, (float('inf'), i, []))
c=[]
c1=[]
while True:
    if a==[]:
        break
    f=heapq.heappop(a)
    v=f[1]
    c.append(f)
    c1.append(v)
    for u in G[v]:
        if u not in c1:
            for i in range(m):
                if a[i][1]==u:
                    g=i
                    break
            if a[g][0]>f[0]+G[v][u]['weight']:
                h=f[2][:]
                h.append(u)
                heapq._siftup(a, g)
                heapq.heappush(a, (f[0]+G[v][u]['weight'], u, h))
for i in range(m):
    if c1[i]==k:
        break
print(c[i][2])
 

Для малого графа программа работает верно. Для большого графа я не смог дождатся конца программы. Как мне дальше оптимизировать?