Discussion :

[Solevita]

Bonjour,

Je cherche à réaliser un calcul mais je commence à me demander si ce que je cherche à faire est réalisable.
j'ai un réseau composée de 145 000 segments stockés au sein d'une table postgres. La relation amont aval est identifier par une colonne possédant identifiant le noeud de départ et d'arrivée du segment.

je cherche à additionner les valeurs d'amont en aval. je pensais partir sur un algo qui part de chaque segment amont et additionne les valeurs jusqu à arriver à la mer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
---- algo---
 
-- fonction (appel sql)
recuplistAmont()
recuplistAval()
recupValAmont(identifiant)
recupVal(identifiant)
sauveVal(identifiant,valeur)
 
listIdSource = recuplistAmont() (contient les identifiants des id les plus en amonts)
listIdExutoire =recuplistAval() (contient les identifiants des id les plus en aval)
 
TANT QUE x DANS listIdSource  FAIRE :
       TANT QUE x PAS DANS listIdExutoire   FAIRE:
                    valAmont = recupIdAmont(x)
                    valEncourt = recupVal(x)
                    valeur = valEncourt + valAmont
                    sauveVal(x,valeur)

Sauf que je me rend compte que juste le fait de boucler sur les listIdSource (liste des segments les plus en amont de mon réseau) ~68 000 entités dans le but de récupérer les segments stockés prend déjà 632 secondes. Ce qui risque de m'être un peu long étant donné qu'à vue de nez le nombre d'opération sera plus au alentour des 650 millions -1 milliards ..

J'avais testé initialement de stocké la table sql dans une liste en pensant naïvement qu'une donnée stockée en ram, les accès au sein de liste python serait plus rapides mais j'ai arrêté le process au bout d'une vingtaine de minutes.

Bref j'avoue que je suis un peu circonspect le nombre d'opération ne me parait pas faramineux mais je commence à me demander si ce que je cherche à faire est réellement possible ?

[jurassic pork]

hello,

j'ai un réseau composée de 145 000 segments stockés au sein d'une table postgres. La relation amont aval est identifier par une colonne possédant identifiant le noeud de départ et d'arrivée du segment.
je cherche à additionner les valeurs d'amont en aval. je pensais partir sur un algo qui part de chaque segment amont et additionne les valeurs jusqu à arriver à la mer :

Je n'ai peut-être rien compris au problème , mais ne serait-il pas de trouver un chemin entre un point de départ et un point d'arrivée ? Sinon le calcul de tous les chemins possibles ? le chemin le plus court ? Une liste de segments ?
Ami calmant, J.P

[Solevita]

hello,

Je n'ai peut-être rien compris au problème , mais ne serait-il pas de trouver un chemin entre un point de départ et un point d'arrivée ? Sinon le calcul de tous les chemins possibles ? le chemin le plus court ? Une liste de segments ?
Ami calmant, J.P

J'ai rajouté une image qui permet de mieux comprendre. Chaque segment possède un identifiant, une valeur, un noeud de départ et un noeud d'arrivé, j'ai besoin d'additionner les valeurs du haut vers le bas (une sorte de forêt inversée)

[wiztricks]

Salut,

Bref j'avoue que je suis un peu circonspect le nombre d'opération ne me parait pas faramineux mais je commence à me demander si ce que je cherche à faire est réellement possible ?

Avant de coder, il faut avoir un algorithme qui tienne la route et qui soit cohérent avec les ressources disponibles. Il y a une rubrique algorithmique rien que pour çà.

- W

[Solevita]

Salut,



Avant de coder, il faut avoir un algorithme qui tienne la route et qui soit cohérent avec les ressources disponibles. Il y a une rubrique algorithmique rien que pour çà.

- W

En algorithmie je tombe surtout sur des cas d'études inverses ( arbres ou forêts). En l'occurrence mon graphe étant orientée, le nombre de possibilité de calcul ne devrait pas être exponentiel comme c'est le cas pour le voyageurs.

[Sve@r]

Bonjour

En l'occurrence mon graphe étant orientée, le nombre de possibilité de calcul ne devrait pas être exponentiel comme c'est le cas pour le voyageurs.

Ce n'est pas exponentiel mais ça reste récursif. A chaque étape tu dois récupérer tous les chemins qui en partent et qui ne sont pas le chemin d'où tu viens. Pour chaque chemin trouvé, tu dois additionner sa valeur à la taille déjà obtenue et rebelote. Et si en fin d'étape tu n'es pas arrivé à la mer (parce que d'après ton dessin certains chemins se terminent en cul de sac), tu dois alors remonter à l'étape précédente en soustrayant cette valeur

J'avais testé initialement de stocké la table sql dans une liste en pensant naïvement qu'une donnée stockée en ram, les accès au sein de liste python serait plus rapides mais j'ai arrêté le process au bout d'une vingtaine de minutes.

Ce n'est pas naif c'est vrai. Les données en RAM sont plus rapidement accessibles que sur disque. Mais la RAM a une taille limitée et au delà ça se met à swapper (sur disque) et là les perfos s'effondrent.

[jurassic pork]

hello,
l'algorithme DFS ( Depth-First Search) se rapproche de ce que tu veux faire.
J'ai publié dans le forum OpenOffice/LibreOffice de developpez une contribution qui utilise cet algorithme en python :
Recherche Chemins dans Diagramme créé dans Draw avec macro en python

voici une macro en python qui recherche dans un diagramme construit dans draw les chemins possibles entre deux formes. La macro utilise l'algorithme DFS pour trouver les chemins. Il y a une boîte de dialogue pour rentrer les formes de départ et d' arrivée et pour lancer le calcul de chemins.

La différence par rapport à toi c'est que je n'utilise pas le nom des segments mais celui des noeuds. Le poids (cost) peut représenter une distance.

Ami calmant, J.P