PostGIS.fr

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

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é!