#1 Wed 21 August 2019 09:57
- guil31
- Participant actif
- Date d'inscription: 22 Jan 2013
- Messages: 79
pgrouting 1.x vers 2.x / Temps de traitement
Bonjour,
Je suis en train de faire passer du code ?crit pour pgrouting 1.x vers 2.x.
J'ai donc substitu? mes fonctions assign_vertex_id() et shortest_path() par pgr_createTopology() et pgr_dijkstra().
Tout ce passe bien et mon code fonctionne correctement avec pgrouting 2.x.
Cependant, pour un m?me jeu de donn?es je passe de 1 minute 50 de temps de traitement ? 6 minutes 30.
Mon jeu de donn?es est un petit jeu de donn?es test et j'ai un peu peur de ce que ?a va donner pour des plus gros volumes de donn?es.
Je cherche donc ? optimiser mes temps de traitements sous pgrouting 2.x
Les fonction shortest_path() et pgr_dijkstra() n?utilisent-t-elles pas toutes les deux dijskra ?
=> Si oui pourquoi cette diff?rence de temps de traitement ?
Dans pgrouting 2.x j'ai vu qu'il existe plusieurs fonctions correspondant ? diff?rentes m?thodes de calcul du plus court chemin (dijkstra, Floyd-Warshall, A*)
=> Est_ce qu'il y a des algorithmes plus rapides que d'autres en temps de traitements ?
Merci d'avance pour vos retours
Claire
Hors ligne
#2 Thu 22 August 2019 10:01
- tumasgiu
- Membre
- Lieu: Ajaccio
- Date d'inscription: 5 Jul 2010
- Messages: 1160
Re: pgrouting 1.x vers 2.x / Temps de traitement
Les fonction shortest_path() et pgr_dijkstra() n?utilisent-t-elles pas toutes les deux dijskra ?
=> Si oui pourquoi cette diff?rence de temps de traitement ?
Selon la doc, shortest_path utilise bien Dijkstra.
Peut être avez vous mal utilisé pgr_createtopology ?
Un index sur une des tables serait peut être judicieux
(couplé avec un VACUUM ANALYZE)
Dans pgrouting 2.x j'ai vu qu'il existe plusieurs fonctions correspondant ? diff?rentes m?thodes de calcul du plus court chemin (dijkstra, Floyd-Warshall, A*)
=> Est_ce qu'il y a des algorithmes plus rapides que d'autres en temps de traitements ?
En fait, cela dépend de la nature de votre graphe.
Par exemple, Floyd-Warshall fonctionne bien sur des graphes denses,
càd ceux dont le nombre d'arêtes est proche du nombre maximum d'arête possible.
Dernière modification par tumasgiu (Thu 22 August 2019 10:20)
Hors ligne
#3 Mon 26 August 2019 17:11
- guil31
- Participant actif
- Date d'inscription: 22 Jan 2013
- Messages: 79
Re: pgrouting 1.x vers 2.x / Temps de traitement
En creusant je me suis rendu compte que ce n'etait pas pgrouting qui me faisait perdre du temps entre postgres 9.1 et 9.5.
Comme certains jeux de donnees etaient volumineux, le code avait ete optimise pour travailler par zone.
Le graphe etait construit sur l'ensemble du jeu de donnees mais ensuite il y avait une selection par intersection spatiale avec une couche de polygones pour ne travailler que par zone.
C'est cette requete d'intersection spatiale qui en passant de postgres 9.1 a 9.5 prenait plus de temps.
La requete spatiale etait du type
Code:
select mon_routing.edge_id,mon_routing.id,mon_routing.source,mon_routing.target,mon_routing.cost,mon_routing.iti,mon_routing.the_geom from mon_routing , mes_zones where ST_Buffer(mes_zones.the_geom, 1000) && mon_routing.the_geom and ST_Intersects(mon_routing.the_geom,ST_Buffer(mes_zones.the_geom, 1000)) IS TRUE and mes_zones.zone_id = '1'
J'ai reecrit la requete de la facon suivante:
Code:
select mon_routing.edge_id,mon_routing.id,mon_routing.source,mon_routing.target,mon_routing.cost,mon_routing.iti,mon_routing.the_geom from mon_routing , mes_zones where mes_zones.zone_id = '1' and st_dwithin(mes_zones.geom, mon_routing.geom, 1000)
Et j'ai gagne un temps phenomenal en 9.5 et aussi en 9.1
Par contre je ne sais pas pourquoi la requete d'origine prenait plus de temps en 9.5 qu'en 9.1
(Il faudrait peut-etre modifier le titre du sujet)
Concernant l'algorithme le plus adapte pour mon jeu de donnees, mes donnees sont assez simple.
Il s'agit d'un reseau FTTH. En general, il n'y a qu'un seul itineraire possible par couple [origine, destination].
Dernière modification par guil31 (Mon 26 August 2019 17:17)
Hors ligne
#4 Mon 26 August 2019 17:45
- tumasgiu
- Membre
- Lieu: Ajaccio
- Date d'inscription: 5 Jul 2010
- Messages: 1160
Re: pgrouting 1.x vers 2.x / Temps de traitement
Et j'ai gagne un temps phenomenal en 9.5 et aussi en 9.1
Par contre je ne sais pas pourquoi la requete d'origine prenait plus de temps en 9.5 qu'en 9.1
(Il faudrait peut-etre modifier le titre du sujet)
Vous pouvez essayer de récupérer le plan des deux requêtes avec EXPLAIN,
pour voir en quoi elles différent.
Concernant l'algorithme le plus adapte pour mon jeu de donnees, mes donnees sont assez simple.
Il s'agit d'un reseau FTTH. En general, il n'y a qu'un seul itineraire possible par couple [origine, destination].
Oui donc j'imagine que votre graphe doit être creux, donc Dijkstra est indiqué.
A* donnera peut être de meilleures performances, mais ne donnera pas forcement
le chemin optimal si l'heuristique n'est pas bonne.
Hors ligne