Discussion :

[santaflam]

Développeurs, Bonjour !

Python codé par un mécanicien :

Code :

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

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

[plxpy]

Salut

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 :

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
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}]

[tyrtamos]

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 :

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

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]

[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

[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 :

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

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 :

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

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".

[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.

[wiztricks]

@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

[santaflam]

Merci !

Tyrtamos, exact pour la nécessité du "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.
...
- 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 :

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

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:] )