2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 14:59 
Здравствуйте!
Было задание для графа записанного в текстовый файл в форме:
Первая строка: число вершин, пробел, число ребер
Остальные строки: номер одной вершины (номера начинаются с 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))
), три минуты против двух секунд. Почему у меня так медленно и как это исправить?

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:19 
Так алгоритм Дейкстры встроенный в networkx тоже на Python!

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:19 
Аватара пользователя
Ну, во-первых, если "встроенный" алгоритм "скомпилирован", то разница вполне ожидаема.

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:20 
Geen в сообщении #1276496 писал(а):
кучи

Какой кучи?

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:22 
Аватара пользователя
Следует иметь ввиду, что почти во всех языках самая медленная (катастрофически) операция это выделение/освобождение памяти...

-- 19.12.2017, 15:23 --

kotenok gav в сообщении #1276497 писал(а):
Geen в сообщении #1276496 писал(а):
кучи

Какой кучи?

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:26 
Аватара пользователя
Вообще при выкладывании кода лучше бы дать переменным понятные имена.

Оцените асимптотику вашей реализации (на первый взгляд очень похоже, что у вас тем лишняя степень по числу вершин затесалась).
Geen в сообщении #1276496 писал(а):
Ну, во-первых, если "встроенный" алгоритм "скомпилирован", то разница вполне ожидаема.
Если модуль написан на питоне (без бинарных вставок), то производительность не должна отличаться от использования такого же кода напрямую.

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:33 
В вашем решении есть две проблемы.
1. Большие константы. Я имею ввиду что некоторые фрагменты написаны так что они выполняются медленнее (в константное число раз) чем их оптимальные варианты. Прежде всего это циклы вида
Код:
for i in range(len(array)):
. Их можно ускорить.
2. Алгоритмическое замедление. Некоторые операции имеют не оптимальную сложность. Вот этот и другие похожие куски можно существенно ускорить:
Код:
if i[1] not in c:
. Вы делаете поиск по массиву, что медленно. Его можно заменить на более быструю поисковую структуру.

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:49 
Ой, один 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 минут.

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 17:20 
Придумал еще одно исправление, сейчас пересчитаю.

-- 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 минут.

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 18:03 
Аватара пользователя
mihaild в сообщении #1276499 писал(а):
Оцените асимптотику вашей реализации

slavav в сообщении #1276500 писал(а):
И ещё раз перечитать описание алгоритма Дейкстры

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение20.12.2017, 07:54 
Может проблема в этом куске?:
Используется синтаксис 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 писал(а):
Оцените асимптотику вашей реализации

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение20.12.2017, 10:01 
Аватара пользователя
kotenok gav в сообщении #1276673 писал(а):
Может, как-то можно заменить этот кусок кода?

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

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

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение20.12.2017, 10:45 
mihaild в сообщении #1276680 писал(а):
Стандартный способ - для каждой строчки посчитать максимальное число раз выполнения (как произведение максимального числа итераций всех циклов, внутри которых она находится, если только не можете доказать, что по какой-то причине максимальное число итераций всех одновременно не достигается), и взять максимум.
Ещё надо учесть сложность используемых готовых функций и конструкций, таких как if i not in c.

 
 
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение21.12.2017, 07:46 
Переписал программу с использованием кучи:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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])
 

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

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group