Question :
J'ai profilé mon programme Python à mort, et il y a une fonction qui ralentit tout. Elle utilise beaucoup les dictionnaires Python, et je ne les ai peut-être pas utilisés de la meilleure façon. Si je ne parviens pas à l'accélérer, je devrai la réécrire en C++. Y a-t-il quelqu'un qui puisse m'aider à l'optimiser en Python ?
J'espère que j'ai donné les bonnes explications et que mon code a un sens pour vous ! Merci d'avance pour toute aide.
Mon code :
Voici la fonction incriminée, profilée à l'aide de line_profiler et kernprof . J'utilise Python 2.7.
Je suis particulièrement intrigué par des choses comme les lignes 363, 389 et 405, où une if avec une comparaison de deux variables semble prendre un temps démesuré.
J'ai envisagé d'utiliser NumPy (comme il le fait pour les matrices éparses) mais je ne pense pas que ce soit approprié car : (1) je n'indexe pas ma matrice en utilisant des entiers (j'utilise des instances d'objets) ; et (2) je ne stocke pas des types de données simples dans la matrice (je stocke des tuples d'un float et d'une instance d'objet). Mais je suis prêt à me laisser convaincre par NumPy. Si quelqu'un connaît les performances des matrices éparses de NumPy par rapport aux tables de hachage de Python, je serais intéressé.
Désolé de ne pas avoir donné un exemple simple que vous pouvez exécuter, mais cette fonction est liée à un projet beaucoup plus vaste et je n'ai pas pu trouver comment mettre en place un exemple simple pour la tester, sans vous donner la moitié de ma base de code !
Timer unit: 3.33366e-10 s
File: routing_distances.py
Function: propagate_distances_node at line 328
Total time: 807.234 s
Line # Hits Time Per Hit % Time Line Contents
328 @profile
329 def propagate_distances_node(self, node_a, cutoff_distance=200):
330
331 # a makes sure its immediate neighbours are correctly in its distance table
332 # because its immediate neighbours may change as binds/folding change
333 737753 3733642341 5060.8 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
334 512120 2077788924 4057.2 0.1 use_neighbour_link = False
335
336 512120 2465798454 4814.9 0.1 if(node_b not in self.node_distances[node_a]): # a doesn't know distance to b
337 15857 66075687 4167.0 0.0 use_neighbour_link = True
338 else: # a does know distance to b
339 496263 2390534838 4817.1 0.1 (node_distance_b_a, next_node) = self.node_distances[node_a][node_b]
340 496263 2058112872 4147.2 0.1 if(node_distance_b_a > neighbour_distance_b_a): # neighbour distance is shorter
341 81 331794 4096.2 0.0 use_neighbour_link = True
342 496182 2665644192 5372.3 0.1 elif((None == next_node) and (float('+inf') == neighbour_distance_b_a)): # direct route that has just broken
343 75 313623 4181.6 0.0 use_neighbour_link = True
344
345 512120 1992514932 3890.7 0.1 if(use_neighbour_link):
346 16013 78149007 4880.3 0.0 self.node_distances[node_a][node_b] = (neighbour_distance_b_a, None)
347 16013 83489949 5213.9 0.0 self.nodes_changed.add(node_a)
348
349 ## Affinity distances update
350 16013 86020794 5371.9 0.0 if((node_a.type == Atom.BINDING_SITE) and (node_b.type == Atom.BINDING_SITE)):
351 164 3950487 24088.3 0.0 self.add_affinityDistance(node_a, node_b, self.chemistry.affinity(node_a.data, node_b.data))
352
353 # a sends its table to all its immediate neighbours
354 737753 3549685140 4811.5 0.1 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
355 512120 2129343210 4157.9 0.1 node_b_changed = False
356
357 # b integrates a's distance table with its own
358 512120 2203821081 4303.3 0.1 node_b_chemical = node_b.chemical
359 512120 2409257898 4704.5 0.1 node_b_distances = node_b_chemical.node_distances[node_b]
360
361 # For all b's routes (to c) that go to a first, update their distances
362 41756882 183992040153 4406.3 7.6 for node_c, (distance_b_c, node_after_b) in node_b_distances.iteritems(): # Think it's ok to modify items while iterating over them (just not insert/delete) (seems to work ok)
363 41244762 172425596985 4180.5 7.1 if(node_after_b == node_a):
364
365 16673654 64255631616 3853.7 2.7 try:
366 16673654 88781802534 5324.7 3.7 distance_b_a_c = neighbour_distance_b_a + self.node_distances[node_a][node_c][0]
367 187083 929898684 4970.5 0.0 except KeyError:
368 187083 1056787479 5648.8 0.0 distance_b_a_c = float('+inf')
369
370 16673654 69374705256 4160.7 2.9 if(distance_b_c != distance_b_a_c): # a's distance to c has changed
371 710083 3136751361 4417.4 0.1 node_b_distances[node_c] = (distance_b_a_c, node_a)
372 710083 2848845276 4012.0 0.1 node_b_changed = True
373
374 ## Affinity distances update
375 710083 3484577241 4907.3 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
376 99592 1591029009 15975.5 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
377
378 # If distance got longer, then ask b's neighbours to update
379 ## TODO: document this!
380 16673654 70998570837 4258.1 2.9 if(distance_b_a_c > distance_b_c):
381 #for (node, neighbour_distance) in node_b_chemical.neighbours[node_b].iteritems():
382 1702852 7413182064 4353.4 0.3 for node in node_b_chemical.neighbours[node_b]:
383 1204903 5912053272 4906.7 0.2 node.chemical.nodes_changed.add(node)
384
385 # Look for routes from a to c that are quicker than ones b knows already
386 42076729 184216680432 4378.1 7.6 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
387
388 41564609 171150289218 4117.7 7.1 node_b_update = False
389 41564609 172040284089 4139.1 7.1 if(node_c == node_b): # a-b path
390 512120 2040112548 3983.7 0.1 pass
391 41052489 169406668962 4126.6 7.0 elif(node_after_a == node_b): # a-b-a-b path
392 16251407 63918804600 3933.1 2.6 pass
393 24801082 101577038778 4095.7 4.2 elif(node_c in node_b_distances): # b can already get to c
394 24004846 103404357180 4307.6 4.3 (distance_b_c, node_after_b) = node_b_distances[node_c]
395 24004846 102717271836 4279.0 4.2 if(node_after_b != node_a): # b doesn't already go to a first
396 7518275 31858204500 4237.4 1.3 distance_b_a_c = neighbour_distance_b_a + distance_a_c
397 7518275 33470022717 4451.8 1.4 if(distance_b_a_c < distance_b_c): # quicker to go via a
398 225357 956440656 4244.1 0.0 node_b_update = True
399 else: # b can't already get to c
400 796236 3415455549 4289.5 0.1 distance_b_a_c = neighbour_distance_b_a + distance_a_c
401 796236 3412145520 4285.3 0.1 if(distance_b_a_c < cutoff_distance): # not too for to go
402 593352 2514800052 4238.3 0.1 node_b_update = True
403
404 ## Affinity distances update
405 41564609 164585250189 3959.7 6.8 if node_b_update:
406 818709 3933555120 4804.6 0.2 node_b_distances[node_c] = (distance_b_a_c, node_a)
407 818709 4151464335 5070.7 0.2 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
408 104293 1704446289 16342.9 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
409 818709 3557529531 4345.3 0.1 node_b_changed = True
410
411 # If any of node b's rows have exceeded the cutoff distance, then remove them
412 42350234 197075504439 4653.5 8.1 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can't use iteritems() here, as deleting from the dictionary
413 41838114 180297579789 4309.4 7.4 if(distance_b_c > cutoff_distance):
414 206296 894881754 4337.9 0.0 del node_b_distances[node_c]
415 206296 860508045 4171.2 0.0 node_b_changed = True
416
417 ## Affinity distances update
418 206296 4698692217 22776.5 0.2 node_b_chemical.del_affinityDistance(node_b, node_c)
419
420 # If we've modified node_b's distance table, tell its chemical to update accordingly
421 512120 2130466347 4160.1 0.1 if(node_b_changed):
422 217858 1201064454 5513.1 0.0 node_b_chemical.nodes_changed.add(node_b)
423
424 # Remove any neighbours that have infinite distance (have just unbound)
425 ## TODO: not sure what difference it makes to do this here rather than above (after updating self.node_distances for neighbours)
426 ## but doing it above seems to break the walker's movement
427 737753 3830386968 5192.0 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].items(): # Can't use iteritems() here, as deleting from the dictionary
428 512120 2249770068 4393.1 0.1 if(neighbour_distance_b_a > cutoff_distance):
429 150 747747 4985.0 0.0 del self.neighbours[node_a][node_b]
430
431 ## Affinity distances update
432 150 2148813 14325.4 0.0 self.del_affinityDistance(node_a, node_b)Explication de mon code :
Cette fonction maintient une matrice de distance éparse représentant la distance du réseau (somme des poids des arêtes sur le chemin le plus court) entre les nœuds d'un (très grand) réseau. Pour travailler avec le tableau complet et utiliser la fonction Algorithme de Floyd-Warshall serait très lent (j'ai d'abord essayé cela, et c'était des ordres de grandeur plus lent que la version actuelle). Mon code utilise donc une matrice éparse pour représenter une version seuillée de la matrice de distance complète (tous les chemins dont la distance est supérieure à 200 unités sont ignorés). La topologie du réseau change au fil du temps, donc cette matrice de distance doit être mise à jour au fil du temps. Pour ce faire, j'utilise une implémentation grossière d'une matrice de distance de type protocole de routage distance-vecteur : chaque nœud du réseau connaît la distance qui le sépare des autres nœuds et du prochain nœud du chemin. Lorsqu'un changement de topologie se produit, le ou les nœuds associés à ce changement mettent à jour leur(s) table(s) de distance en conséquence, et en informent leurs voisins immédiats. L'information est diffusée dans le réseau par les nœuds qui envoient leurs tables de distance à leurs voisins, qui mettent à jour leurs tables de distance et les diffusent à leurs voisins.
Il existe un objet représentant la matrice de distance : self.node_distances . Il s'agit d'un dictionnaire faisant correspondre les nœuds aux tables de routage. Un nœud est un objet que j'ai défini. Une table de routage est un dictionnaire faisant correspondre des noeuds à des tuples de (distance, next_node). Distance est la distance graphique entre le noeud_a et le noeud_b, et next_node est le voisin du noeud_a que vous devez visiter en premier, sur le chemin entre le noeud_a et le noeud_b. Un next_node de None indique que les nœuds_a et node_b sont des voisins du graphe. Par exemple, un exemple de matrice de distance pourrait être :
self.node_distances = { node_1 : { node_2 : (2.0, None),
node_3 : (5.7, node_2),
node_5 : (22.9, node_2) },
node_2 : { node_1 : (2.0, None),
node_3 : (3.7, None),
node_5 : (20.9, node_7)},
...etc...En raison des changements de topologie, deux nœuds qui étaient éloignés (ou pas du tout connectés) peuvent devenir proches. Lorsque cela se produit, des entrées sont ajoutées à cette matrice. En raison du seuillage, deux nœuds peuvent devenir trop éloignés l'un de l'autre pour être pris en compte. Dans ce cas, des entrées sont supprimées de cette matrice.
El self.neighbours est similaire à self.node_distances mais contient des informations sur les liens directs (arêtes) du réseau. self.neighbours est continuellement modifié à l'extérieur de cette fonction, par la réaction chimique. C'est de là que proviennent les modifications de la topologie du réseau.
La fonction réelle avec laquelle j'ai des problèmes : propagate_distances_node() exécute une étape de la protocole de routage distance-vecteur . Étant donné un nœud, node_a la fonction s'assure que node_a Les voisins de l'utilisateur sont correctement inscrits dans la matrice de distance (la topologie change). La fonction envoie ensuite node_a de la table de routage de l'entreprise vers tous les node_a dans le réseau. Il intègre node_a avec la table de routage de chaque voisin.
Dans le reste de mon programme, le propagate_distances_node() est appelée à plusieurs reprises, jusqu'à ce que la matrice de distance converge. Un ensemble, self.nodes_changed est maintenue, des noeuds qui ont modifié leur table de routage depuis la dernière mise à jour. À chaque itération de mon algorithme, un sous-ensemble aléatoire de ces nœuds est choisi et propagate_distances_node() est appelé sur eux. Cela signifie que les nœuds diffusent leurs tables de routage de manière asynchrone et stochastique. Cet algorithme converge vers la vraie matrice de distance lorsque l'ensemble self.nodes_changed devient vide.
Les parties "distances d'affinité" ( add_affinityDistance y del_affinityDistance ) sont un cache d'une (petite) sous-matrice de la matrice de distance, qui est utilisée par une autre partie du programme.
La raison pour laquelle je fais cela est que je simule des analogues informatiques de produits chimiques participant à des réactions, dans le cadre de mon doctorat. Un "produit chimique" est un graphe d'"atomes" (nœuds du graphe). La liaison entre deux produits chimiques est simulée par la jonction de leurs deux graphes par de nouvelles arêtes. Une réaction chimique se produit (par un processus compliqué qui n'est pas pertinent ici), modifiant la topologie du graphe. Mais ce qui se passe dans la réaction dépend de la distance qui sépare les différents atomes qui composent les produits chimiques. Ainsi, pour chaque atome de la simulation, je veux savoir de quels autres atomes il est proche. Une matrice de distance éparse et seuillée est le moyen le plus efficace de stocker ces informations. Comme la topologie du réseau change au fur et à mesure que la réaction se produit, je dois mettre à jour la matrice. A protocole de routage distance-vecteur est le moyen le plus rapide que j'ai trouvé pour faire cela. Je n'ai pas besoin d'un protocole de routage plus compliqué, car des choses comme les boucles de routage ne se produisent pas dans mon application particulière (en raison de la façon dont mes produits chimiques sont structurés). La raison pour laquelle je le fais de manière stochastique est que je peux imbriquer les processus de réaction chimique avec l'étalement de la distance, et simuler un produit chimique changeant progressivement de forme au fil du temps au fur et à mesure que la réaction se produit (plutôt que de changer de forme instantanément).
El self dans cette fonction est un objet représentant un produit chimique. Les nœuds dans self.node_distances.keys() sont les atomes qui composent le produit chimique. Les nœuds dans self.node_distances[node_x].keys() sont des nœuds du produit chimique et potentiellement des nœuds de tout produit chimique auquel le produit chimique est lié (et avec lequel il réagit).
Mise à jour :
J'ai essayé de remplacer chaque instance de node_x == node_y con node_x is node_y (conformément au commentaire de @Sven Marnach), mais ça a ralenti les choses ! (Je ne m'y attendais pas !) Mon profil original prenait 807.234s pour s'exécuter, mais avec cette modification il est passé à 895.895s. Désolé, je faisais mal le profilage ! J'utilisais line_by_line, qui (sur mon code) avait beaucoup trop de variance (cette différence de ~90 secondes était dans le bruit). En le profilant correctement, is est infiniment plus rapide que == . Utilisation de CProfile mon code avec == a pris 34.394s, mais avec is il a fallu 33.535s (ce que je peux confirmer est hors du bruit).
Mise à jour : Bibliothèques existantes
Je ne suis pas sûr qu'il existe une bibliothèque existante capable de faire ce que je veux, car mes exigences sont inhabituelles : J'ai besoin de calculer les longueurs des plus courts chemins entre toutes les paires de nœuds dans un graphe pondéré et non dirigé. Je ne me préoccupe que des longueurs de chemin qui sont inférieures à une valeur seuil. Après avoir calculé les longueurs de chemin, j'apporte une petite modification à la topologie du réseau (ajout ou suppression d'une arête), puis je veux recalculer les longueurs de chemin. Mes graphes sont énormes par rapport à la valeur seuil (à partir d'un nœud donné, la plupart du graphe est plus éloigné que le seuil), et donc les changements de topologie n'affectent pas la plupart des longueurs de chemin les plus courts. C'est la raison pour laquelle j'utilise l'algorithme de routage : parce qu'il diffuse l'information sur les changements de topologie à travers la structure du graphe, et que je peux arrêter de la diffuser lorsqu'elle a dépassé le seuil. Je peux utiliser les informations précédentes sur les chemins (d'avant le changement de topologie) pour accélérer le calcul. C'est pourquoi je pense que mon algorithme sera plus rapide que toutes les implémentations de bibliothèques d'algorithmes de plus court chemin. Je n'ai jamais vu d'algorithmes de routage utilisés en dehors du routage de paquets dans des réseaux physiques (mais si quelqu'un l'a fait, je serais intéressé).
NetworkX a été suggéré par @Thomas K. Il a beaucoup d'algorithmes pour calculer les plus courts chemins. Il dispose d'un algorithme pour calculer le longueurs des plus courts chemins de toutes les paires avec une coupure (ce qui est ce que je veux), mais il ne fonctionne que sur des graphes non pondérés (les miens sont pondérés). Malheureusement, son algorithmes pour les graphes pondérés ne permettent pas l'utilisation d'un seuil (ce qui pourrait les rendre lents pour mes graphiques). Et aucun de ses algorithmes ne semble supporter l'utilisation de chemins précalculés sur un réseau très similaire (c'est-à-dire le routage).
igraphe est une autre bibliothèque de graphiques que je connais, mais en regardant sa documentation Je n'ai rien trouvé sur les chemins les plus courts. Mais je pourrais l'avoir manqué - sa documentation ne semble pas très complète.
NumPy pourrait être possible, grâce au commentaire de @9000. Je peux stocker ma matrice éparse dans un tableau NumPy si j'attribue un entier unique à chaque instance de mes nœuds. Je peux alors indexer un tableau NumPy avec des entiers au lieu d'instances de nœuds. J'aurai également besoin de deux tableaux NumPy : un pour les distances et un pour les références "next_node". Cela pourrait être plus rapide que d'utiliser les dictionnaires Python (je ne sais pas encore).
Quelqu'un connaît-il d'autres bibliothèques qui pourraient être utiles ?
Mise à jour : Utilisation de la mémoire
J'utilise Windows (XP), voici donc quelques informations sur l'utilisation de la mémoire, provenant de Explorateur de processus . L'utilisation du CPU est de 50% car j'ai une machine à deux cœurs.
Mon programme n'est pas à court de RAM et ne commence pas à frapper le swap. Vous pouvez le voir d'après les chiffres, et d'après le graphique IO qui n'a aucune activité. Les pics sur le graphique IO sont ceux que le programme imprime à l'écran pour dire comment il se comporte.
Cependant, mon programme utilise de plus en plus de RAM au fil du temps, ce qui n'est probablement pas une bonne chose (mais il n'utilise pas beaucoup de RAM dans l'ensemble, c'est pourquoi je n'ai pas remarqué l'augmentation jusqu'à maintenant).
Et la distance entre les pics sur le graphique IO augmente avec le temps. C'est mauvais - mon programme imprime à l'écran toutes les 100 000 itérations, ce qui signifie que chaque itération prend plus de temps à s'exécuter au fil du temps... J'ai confirmé cela en faisant une longue exécution de mon programme et en mesurant le temps entre les instructions d'impression (le temps entre chaque 10 000 itérations du programme). Ce temps devrait être constant, mais comme vous pouvez le voir sur le graphique, il augmente linéairement... il y a donc quelque chose qui se passe. (Le bruit sur ce graphique est dû au fait que mon programme utilise beaucoup de nombres aléatoires, donc le temps pour chaque itération varie).
Après que mon programme ait été exécuté pendant une longue période, l'utilisation de la mémoire ressemble à ceci (donc il ne manque pas de RAM) :
