2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 14:59 


21/05/16
4292
Аделаида
Здравствуйте!
Было задание для графа записанного в текстовый файл в форме:
Первая строка: число вершин, пробел, число ребер
Остальные строки: номер одной вершины (номера начинаются с 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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:19 


21/05/16
4292
Аделаида
Так алгоритм Дейкстры встроенный в networkx тоже на Python!

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:19 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:20 


21/05/16
4292
Аделаида
Geen в сообщении #1276496 писал(а):
кучи

Какой кучи?

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


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

-- 19.12.2017, 15:23 --

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

Какой кучи?

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

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


16/07/14
8355
Цюрих
Вообще при выкладывании кода лучше бы дать переменным понятные имена.

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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:33 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение19.12.2017, 15:49 


21/05/16
4292
Аделаида
Ой, один 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 


21/05/16
4292
Аделаида
Придумал еще одно исправление, сейчас пересчитаю.

-- 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 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
mihaild в сообщении #1276499 писал(а):
Оцените асимптотику вашей реализации

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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение20.12.2017, 07:54 


21/05/16
4292
Аделаида
Может проблема в этом куске?:
Используется синтаксис 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 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
kotenok gav в сообщении #1276673 писал(а):
Может, как-то можно заменить этот кусок кода?

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

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

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение20.12.2017, 10:45 
Заслуженный участник


02/08/11
6874
mihaild в сообщении #1276680 писал(а):
Стандартный способ - для каждой строчки посчитать максимальное число раз выполнения (как произведение максимального числа итераций всех циклов, внутри которых она находится, если только не можете доказать, что по какой-то причине максимальное число итераций всех одновременно не достигается), и взять максимум.
Ещё надо учесть сложность используемых готовых функций и конструкций, таких как if i not in c.

 Профиль  
                  
 
 Re: Оптимизация реализации алгоритма Дейкстры на Python
Сообщение21.12.2017, 07:46 


21/05/16
4292
Аделаида
Переписал программу с использованием кучи:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group