Module de routing de Postgis

Bonjour,

Après avoir tester avec succes les fonctions de routing du module Dijkstra sur 20000 tronçons de rue, je rencontre de gros problèmes de performances sur un table de 15 millions d'enregistrements.

Existe-t'il des possibilités d'optimisation de ce module ?

Merci

ERIC

Posted in Généraliste | WINDOWS Vous devez vous connecter ou vous enregistrer pour écrire des commentaires | sujet précédent | sujet suivant | printer friendly version | 3953 lectures

Posté par eric le 17 Juillet, 2006 - 21:36.

djay | 18 Juillet, 2006 - 16:31

Salut Eric,
je tiens tout d'abord à préciser que l'algorithmie n'a jamais été mon point fort.

Cependant je pense qu'il existe en effet une optimisation possible si les files de priorités sont actuellement implémentées sous la forme de tableaux linéaires. En effet dans ce cas la complexité de l'algorithme est en O(S ²), ce qui expliquerait les problèmes que tu as rencontré, cela reste à vérifier (lecture du code source du module de routing).

Néanmoins si tu utilises des files d'attentes utilisant une structure de donnée "plus complexe", un tas, tu obtiendras alors une complexité en O((S+A) ln S). De plus si tu utilises des files de Fibonacci tu obtiendras alors une complexité encore plus faible, en O(S ln S + A).

Merci d'avance de nous donner des informations sur tes recherches sur le sujet.

ps: je te conseille vivement le livre publié chez Dunod et intitulé "Introduction à l'algorithmie" pour de plus ample informations sur le sujet, ou encore google avec un zest de courage.

--
Gérald Fenoy

david | 18 Juillet, 2006 - 14:56

bonjour

Je pense que le mieux c'est de vous adresser directement à développeurs de CartoWeb et de poser votre question sur leur mailing-list!

Là j'avoue que je ne saurais vous répondre

Peux être s'agit-il simplement de paramètres de PostgreSQL qu'il faudrait revoir
pour améliorer les performances sur votre grosse table! Je n'ai vraiment aucun e idée

Désolé!

Accéder aux archives

« Novembre 2024  
Lun Mar Mer Jeu Ven Sam Dim
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  

Ouverture de session

Qui est en ligne

Il y a actuellement 1 utilisateur et 747 invités en ligne.
Locations of visitors to this page
Drupal Top Sites - Ultimate Drupal Exposure