Remplissage de LISTE à partir de DICO.Temps de calcul explose !

Version imprimable

Développeurs, Bonjour !

Python codé par un mécanicien :
Code:

1 2 3 4 5 6 7 8 # VertexList = [ {'X':10, 'Y':10, 'VertexId':103}, {...} ... ] LISTE DE DICTIONNAIRES # VertexListList = [] i = 1 while ( i <= len ( VertexList ) ) : VertexListList.append ( next ( ( [ item ['X'], item ['Y'] ] for item in VertexList if item ['VertexId'] == i ) ) ) i = i + 1
J'ordonne donc une liste par recherche de la clef 'VertexId' de ses éléments (des dicos).

Cette boucle explose en temps de calcul, environ 1mn pour seulement 25000 dictionnaires dans la liste.

Y a-t-il une méthode plus rapide que celle-là en temps de calcul ?

Merci !
SF

Salut

Citation:

Envoyé par santaflam

Y a-t-il une méthode plus rapide que celle-là en temps de calcul ?

oh que oui ! Tout bêtement en utilisant la méthode sort :

Code:

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
>>> import random
>>> from time import time
>>> 
>>> idents = range(25000)
>>> random.shuffle(idents)
>>> # petite verif
... print idents[:10]
[20527, 3454, 14104, 12341, 23876, 15896, 16088, 11081, 4679, 24899]
>>> 
>>> VertexList = [ {'X':0., 'Y':0., 'VertexId':i } for i in idents ] 
>>> 
>>> t0=time(); VertexList.sort(key=lambda elt: elt['VertexId']);time()-t0 
0.0328829288482666
>>> 
>>> # autre verif
... import pprint
>>> pprint.pprint(VertexList[:10])
[{'VertexId': 0, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 1, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 2, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 3, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 4, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 5, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 6, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 7, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 8, 'X': 0.0, 'Y': 0.0},
 {'VertexId': 9, 'X': 0.0, 'Y': 0.0}]

Bonjour,

Il y a au moins 2 choses qui sont chères en temps:

- le while qui nécessite de calculer à chaque boucle len(...) alors que cette longueur ne change pas.

- le if item ['VertexId'] == i qui nécessitera de parcourir la liste 25000 fois

Si j'ai bien compris l'objectif, c'est de faire une liste des [x, y] pris dans l'ordre des valeurs des clés 'VertexId'.

Dans ce cas, il est préférable de mettre les dico dans l'ordre de ces valeurs par un simple tri de la liste VertexList (les tris en Python sont très rapides).

Puis de construire la nouvelle liste par une simple "compréhension de liste":

Voilà ma proposition:
Code:

1 2 3 4 # tri de la liste pour avoir les dicos dans le bon ordre VertexList.sort(key=lambda v: v['VertexId']) # construction de la nouvelle liste des [x, y] VertexListList = [[dico['X'], dico['Y']] for dico in VertexList]
Essaie et donne le temps que tu obtiens!

[grillé par plxpy]

06/12/2014, 11h24
wiztricks

Salut,

Les choses seraient peut être plus simple si VextexList était construite de sorte à ce que VextexList[id] = VextexList[id]['VertexId'], ou soit un dict dont la clé soit 'VertexId'.

- W
07/12/2014, 01h15
santaflam
Merci pour vos réponses respectives !

Je peux me contenter du nouveau temps de calcul, néanmoins j'ai fait la comparaison suivante :

1.
Votre solution ( sort et réecriture de la liste ):
Temps 0,2344 s
Code:

1 2 3 VertexList.sort ( key=lambda elt: elt['VertexId'] ) VertexListList = [ [ item ['X'], item ['Y'] ] for item in VertexList ]
2.
Et une autre solution, basique, une itération et un test sur la clef:
Temps 0,2031 s
Code:

1 2 3 4 5 6 i=1 for item in VertexList : if item ['VertexId'] == i : VertexListList.append ( [ item ['X'], item ['Y'] ] ) i=i+1
N'est-ce pas curieux que cette 2ième méthode soit plus rapide (0,2031 contre 0,2344 s) , bien que paraissant assez loourde, par le if qui itère sur toute la liste ?

@wiztricks:
A sa construction la liste de départ Vertexlist est ordonnée effectivement. Mais elle est sujette à modification ultérieurement, voilà pourquoi la nécessité d'un "sort".
07/12/2014, 06h10
tyrtamos

Bonjour,

A mon avis, le 2ème code ne donne le bon résultat que si le tri est déjà fait! Sinon, la liste finale est incomplète.

Et si la 1ère liste est déjà triée, il faut retirer le "sort" du 1er code pour comparer les temps de calcul.

Cependant, j'ai déjà remarqué que les "compréhensions de liste" sont plus concises mais pas forcément plus rapides que les boucles classiques.
07/12/2014, 11h47
wiztricks

Citation:

Envoyé par santaflam

@wiztricks:
A sa construction la liste de départ Vertexlist est ordonnée effectivement. Mais elle est sujette à modification ultérieurement, voilà pourquoi la nécessité d'un "sort".

Si l'ordre des éléments dans la liste a quelque importance, pourquoi le changer par la suite?
De plus, si vous vous efforciez de préserver l'ordre, plus besoin d'un dict contenant le VextexId - {'X':0., 'Y':0., 'VertexId':i } - puisque VextexList[id] = VextexList[id]['VertexId'] serait toujours vrai.
note: virer VertexId, vous obligerait aussi à préserver l'ordre
Enfin, si les performances vous inquiètent - ce que je comprend tout à fait à cause du nombre d'éléments - pourquoi ne pas construire une liste ordonnée de listes(ou de tuples) de coordonnées? Dans ce cas, l'opération que vous êtes en train de faire i.e. construire la liste des coordonnées serait déjà faite.

Tout çà pour dire que si l'organisation initiale de vos données et le choix des structures n'est pas adapté, il faut peut être en changer. Et avec un langage comme Python "changer" n'est pas si compliqué...

- W
08/12/2014, 23h46
santaflam
Merci !

Tyrtamos, exact pour la nécessité du "sort".

Citation:

Envoyé par wiztricks

Si l'ordre des éléments dans la liste a quelque importance, pourquoi le changer par la suite?
De plus, si vous vous efforciez de préserver l'ordre, plus besoin d'un dict contenant le VextexId - {'X':0., 'Y':0., 'VertexId':i } - puisque VextexList[id] = VextexList[id]['VertexId'] serait toujours vrai.
note: virer VertexId, vous obligerait aussi à préserver l'ordre
Enfin, si les performances vous inquiètent - ce que je comprend tout à fait à cause du nombre d'éléments - pourquoi ne pas construire une liste ordonnée de listes(ou de tuples) de coordonnées? Dans ce cas, l'opération que vous êtes en train de faire i.e. construire la liste des coordonnées serait déjà faite.
...
- W

J'ai introduit des dicos parce que je voulais être sûr de ne pas prendre une vitesse pour une coordonnée par exemple.
Je dois construire un enregistrement de points avec leurs attributs respectifs: X(coord), Y(coord), V(vitesse), P (oids), VertexId etc
L'ordre importe parce qu'il me faut relier ces points sur un graphique.
L'ordre est muable parce que je peux effacer un point du graphique et le remplacer par une série de points.
J'ai bien compris que si j'ordonne la liste alors:
"VextexList[id] = VextexList[id]['VertexId'] serait toujours vrai."

Une liste de listes aurait donc l'avantage d'être plus rapide, si j'ai bien compris ?

Remarque indépendante:
C'était assez pratique de faire comme suit: s'il trouve une des clefs dans le premier champ de l'enregistrement field, il actualise cette clef ...
Assez cours comme écriture, au lieu de if field [0]=X, puis if field[0]=Y etc ... dans le cas où je passe par des listes. Mais ceci n'affecte pas le temps de calcul je pense ...
Code:

1 2 3 4 5 # field = enregistrement lu dans fichier texte Vertx = {'X':10, 'Y':10, 'V':800.0, 'VertexId':103} etc } if field [0] in Vertx : Vertx [ field [0] ] = float ( field [1:] )
09/12/2014, 08h01
wiztricks

Salut?

Citation:

Envoyé par santaflam

J'ai introduit des dicos parce que je voulais être sûr de ne pas prendre une vitesse pour une coordonnée par exemple.
Je dois construire un enregistrement de points avec leurs attributs respectifs: X(coord), Y(coord), V(vitesse), P (oids), VertexId etc
L'ordre importe parce qu'il me faut relier ces points sur un graphique.
L'ordre est muable parce que je peux effacer un point du graphique et le remplacer par une série de points.
J'ai bien compris que si j'ordonne la liste alors:
"VextexList[id] = VextexList[id]['VertexId'] serait toujours vrai."

Une liste de listes aurait donc l'avantage d'être plus rapide, si j'ai bien compris ?

Si l'ordre est donné par VertexID comment gérez vous la suppression et l'ajout de Points?
Est-ce que vous recalculez les VertexID suivants?
Intuitivement, ça ferait beaucoup d'opérations qu'une liste (peut être pas la liste de base Python) éviterait.
Et in fine, vous n'auriez pas à faire un "sort" pour ranger les Points: ils seraient toujours bien rangés.

- W
12/12/2014, 02h10
santaflam
Citation:

Envoyé par wiztricks

...
Si l'ordre est donné par VertexID comment gérez vous la suppression et l'ajout de Points?
Est-ce que vous recalculez les VertexID suivants?
Intuitivement, ça ferait beaucoup d'opérations qu'une liste (peut être pas la liste de base Python) éviterait.
Et in fine, vous n'auriez pas à faire un "sort" pour ranger les Points: ils seraient toujours bien rangés.

Salut et merci !

Oui, pour l'ajout ou la suppression de points, je recalcule à partir du dernier point non modifié (pas encore codé cette partie)
Je recherche donc, dans la liste,les coordonnées du point sélectionné.
Avec liste de listes:
Code:

1 2 3 4 5 6 7 8 VertexList = [ [0.0, 0.0, 0.0], [...] ] point_selectionne = [ 50.748 , ... ] for item in VertexList : if item [0] == 50.748 : print ( VertexList.index (item) ) ...
Au final, un gain de temps effectivement, mais un test sur 70 000 points montre des écarts de temps de calcul très faibles.
12/12/2014, 07h43
wiztricks

Citation:

Envoyé par santaflam

Au final, un gain de temps effectivement, mais un test sur 70 000 points montre des écarts de temps de calcul très faibles.

A mon sens, le plus important est de préserver l'ordre (en virant VertexId).
Pour ce qui est d'une recherche sur 70.000 points,...
S'il faut en faire beaucoup, il va falloir indexer tout ce bazar...
Comme c'est du code assez complexe, peut être pourriez-vous regarder ce que çà donne avec une base de donnée sqlite en mémoire (et indexer les colonnes). Ceci dit, il est peut être préférable d'avancer sur votre code pour avoir une vue d'ensemble des opérations effectuées avant de se lancer la dedans.

- W
12/12/2014, 08h07
santaflam

Citation:

Envoyé par wiztricks

A mon sens, le plus important est de préserver l'ordre (en virant VertexId).
Pour ce qui est d'une recherche sur 70.000 points,...
S'il faut en faire beaucoup, il va falloir indexer tout ce bazar...
Comme c'est du code assez complexe, peut être pourriez-vous regarder ce que çà donne avec une base de donnée sqlite en mémoire (et indexer les colonnes). Ceci dit, il est peut être préférable d'avancer sur votre code pour avoir une vue d'ensemble des opérations effectuées avant de se lancer la dedans.
- W

Salut,

je me demandais comment on faisait ça de manière professionnelle ... car en effet ce que j'aimerais c'est avoir une interaction très rapide entre le graphique (tracé de points) et la liste qui est "affichée" dans un éditeur de texte, et ce dans les 2 sens, c'est-à-dire je vais à une ligne quelconque dans l'éditeur (celà correspond à 1 point dans la liste) et le point va immédiatement être illuminé sur le graphique et réciproquement je sélectionne un point du graphique, le curseur va à la ligne correspondante dans l'éditeur.
Je vais en effet avancer dans le projet pour voir où sont les limites, le cas échéant voir avec sqlite (que je ne connais pas non plus).
12/12/2014, 10h24
wiztricks

Citation:

Envoyé par santaflam

je me demandais comment on faisait ça de manière professionnelle ... car en effet ce que j'aimerais c'est avoir une interaction très rapide entre le graphique (tracé de points) et la liste qui est "affichée" dans un éditeur de texte, et ce dans les 2 sens, c'est-à-dire je vais à une ligne quelconque dans l'éditeur (celà correspond à 1 point dans la liste) et le point va immédiatement être illuminé sur le graphique et réciproquement je sélectionne un point du graphique, le curseur va à la ligne correspondante dans l'éditeur.
Je vais en effet avancer dans le projet pour voir où sont les limites, le cas échéant voir avec sqlite (que je ne connais pas non plus).

Les solutions ne seront pas les mêmes pour des listes de 1000, 10000, 100000,... Bien sûr tout dépend de l'ensemble des opérations qu'on va faire dessus mais réduire la taille du problème d'un facteur 10 ou 100 sera certainement la première possibilité à étudier. Si ce n'est pas possible, il faut trouver des organisations de données et des algorithmes adaptés. Problème: ce qui sera bon pour certains traitements pourra être très moyen dans d'autres cas. Sans vision d'ensemble impossible de faire des choix raisonnables.
Comme les structures de données vont constituer l'ossature du programme, "en général", on y réfléchit beaucoup avant de se lancer dans le codage car si c'est dégueu, il faudra probablement beaucoup recoder.
Ceci dit, vous avez la chance aujourd'hui d'avoir accès à pas mal de solutions open source. Ca vaut le coup de regarder ce qui a été fait pour des projets semblables aux votres pour s'en inspirer.

- W