Блог

У меня есть график networkx G , который содержит данные станций остановок общественного транспорта в виде узлов, а ребра представляют все маршруты сети общественного транспорта. У меня есть скрипт, который возвращает пару координат точек ( [x_coord1, y_coord1] и [x_coord2, y_coord2] ) определенное количество времени.

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

Я сделал это, и это работает очень хорошо, но это занимает слишком много времени. Для выполнения всей функции требуется около 600-850 мс (см. Код ниже), что слишком долго (так как мне нужно делать это в цикле примерно для 10 миллионов путей).

Ниже приведена функция, которую я написал, зная, что:

• A — это массив списков всех значений lon / lat для всех узлов G в формате array([[x1, y1], [x2, y2], [x3, y3], ...])
• coord_source в формате [x_coord1, y_coord1] — это первая точка пары, возвращенная предыдущим скриптом
• coord_targ в формате [x_coord2, y_coord2] является второй точкой пары, возвращенной предыдущим скриптом

 def short_path(A, coord_source, coord_targ, G):
    get1 = A[spatial.KDTree(A).query(coord_source)[1]]  ###--- Gets the closest stop station to pt1 and %time of this line gives a walltime of 150 ms approximately
    get2 = A[spatial.KDTree(A).query(coord_targ)[1]]  ###--- same for this one but for pt2
    
    for k in G.nodes().keys():
        lon = G.nodes()[k]['stop_lon']
        lat = G.nodes()[k]['stop_lat']            

        if (lon == get1[0]) amp; (lat == get1[1]):
            source = k
        if (lon == get2[0]) amp; (lat == get2[1]):
            target = k
    
    pcc = nx.shortest_path(G, source=source, target=target, weight='time')  ###--- %time of this line gives a walltime of 200 ms
 

Есть ли способ заставить мой скрипт работать быстрее? Также, пожалуйста, скажите мне, если некоторые части недостаточно понятны, и я сделаю все возможное, чтобы объяснить их лучше.