Pregunta:Optimización del pitón código de acceso diccionario
que he perfilado mi programa de Python para la muerte, y no hay una función que se está desacelerando todo abajo. Utiliza diccionarios de Python en gran medida, por lo que puede que no los haya usado de la mejor manera. Si no puedo ejecutarlo más rápido, tendré que volver a escribirlo en C++, entonces ¿hay alguien que pueda ayudarme a optimizarlo en Python?
¡Espero haber dado el tipo correcto de explicación, y que usted puede dar sentido a mi código! Gracias de antemano por cualquier ayuda.
Mi código:
Ésta es la función problemática, perfilada mediante line_profiler and kernprof. Estoy ejecutando Python 2.7
Estoy particularmente desconcertado por cosas como las líneas 363, 389 y 405, donde una declaración if con una comparación de dos variables parece tomar una cantidad de tiempo desorbitada.
He considerado usar NumPy (como lo hace con las matrices dispersas) pero no creo que sea apropiado porque: (1) No estoy indexando mi matriz usando enteros (estoy usando instancias de objeto); y (2) No estoy almacenando tipos de datos simples en la matriz (estoy almacenando tuplas de un flotante y una instancia de objeto). Pero estoy dispuesto a ser persuadido sobre NumPy. Si alguien sabe acerca del escaso rendimiento de la matriz de NumPy frente a las tablas hash de Python, me interesaría.
Lo siento, no he dado un ejemplo simple que se puede ejecutar, pero esta función está vinculada a un proyecto mucho más grande y no pude encontrar la manera de configurar un ejemplo simple para probarlo, sin darle la mitad de mi código base!
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():
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)
Explicación de mi código:
Esta función mantiene una matriz de distancia escasa que representa la distancia de red (suma de los pesos de borde en la ruta más corta) entre los nodos en un (muy grande) de red. Para trabajar con la tabla completa y usar el Floyd-Warshall algorithm sería muy lento. (Intenté esto primero, y fue en órdenes de magnitud más lentos que la versión actual.) Entonces mi código usa una matriz dispersa para representar una versión con umbral de la matriz de distancia completa (se ignoran las rutas con una distancia superior a 200 unidades). La topología de la red cambia con el tiempo, por lo que esta matriz de distancia necesita actualizarse a lo largo del tiempo. Para hacer esto, estoy usando una implementación aproximada de distance-vector routing protocol: cada nodo en la red conoce la distancia entre cada nodo y el siguiente nodo en la ruta. Cuando ocurre un cambio de topología, los nodos asociados con este cambio actualizan sus tablas de distancia en consecuencia y se lo dicen a sus vecinos inmediatos. La información se propaga a través de la red por nodos que envían sus tablas de distancia a sus vecinos, quienes actualizan sus tablas de distancia y las difunden a sus vecinos.
Hay un objeto que representa la matriz de distancia: self.node_distances. Este es un mapa de nodos de mapeo a tablas de enrutamiento. Un nodo es un objeto que he definido. Una tabla de enrutamiento es un diccionario de asignación de nodos a tuplas de (distancia, siguiente_nodo). La distancia es la distancia gráfica entre node_a y node_b, y next_node es el vecino de node_a al que debe ir primero, en la ruta entre node_a y node_b. Un next_node de None indica que node_a y node_b son vecinos de gráfico.Por ejemplo, una muestra de una matriz de distancia podría ser:
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...
Debido a cambios en la topología, dos nodos que eran muy separados (o no conectado en todo) puede llegar a ser de cerca. Cuando esto sucede, las entradas se agregan a esta matriz. Debido al umbral, dos nodos pueden separarse demasiado para preocuparse. Cuando esto sucede, las entradas se eliminan de esta matriz.
La matriz self.neighbours es similar a self.node_distances, pero contiene información sobre los enlaces directos (bordes) en la red. self.neighbours continuamente se modifica externamente a esta función, por la reacción química. Aquí es de donde provienen los cambios de topología de red.
La función real con la que estoy teniendo problemas: propagate_distances_node() realiza un paso del distance-vector routing protocol. Dado un nodo, node_a, la función se asegura de que los vecinos node_a estén correctamente en la matriz de distancia (cambios de topología). La función luego envía la tabla de enrutamiento node_a a todos los vecinos inmediatos de node_a en la red. Integra la tabla de enrutamiento node_a con la tabla de enrutamiento de cada vecino.
En el resto de mi programa, se llama repetidamente a la función propagate_distances_node(), hasta que la matriz de distancia converja. Se mantiene un conjunto, self.nodes_changed, de los nodos que han cambiado su tabla de rutas desde la última actualización. En cada iteración de mi algoritmo, se elige un subconjunto aleatorio de estos nodos y se llama a ellos al propagate_distances_node(). Esto significa que los nodos distribuyen sus tablas de enrutamiento de forma asíncrona y estocástica. Este algoritmo converge en la matriz de distancia real cuando el conjunto self.nodes_changed se vacía.
Las partes de "distancias de afinidad" (add_affinityDistance y del_affinityDistance) son un caché de una (pequeña) submatriz de la matriz de distancia, que es utilizada por una parte diferente del programa.
La razón por la que hago esto es porque estoy simulando análogos computacionales de sustancias químicas que participan en reacciones, como parte de mi doctorado. Un "producto químico" es un gráfico de "átomos" (nodos en el gráfico). Dos sustancias químicas que se unen juntas se simulan cuando sus dos gráficos se unen por nuevos bordes. Se produce una reacción química (mediante un proceso complicado que no es relevante aquí), cambiando la topología del gráfico. Pero lo que sucede en la reacción depende de qué tan separados estén los diferentes átomos que componen los productos químicos. Entonces, para cada átomo en la simulación, quiero saber a qué otros átomos se aproxima. Una matriz de distancia escasa y con umbral es la forma más eficiente de almacenar esta información. Como la topología de la red cambia a medida que se produce la reacción, necesito actualizar la matriz. Un distance-vector routing protocol es la forma más rápida que se me ocurre de hacer esto. No necesito un protocolo de enrutamiento más compatible, porque cosas como los bucles de enrutamiento no ocurren en mi aplicación particular (debido a la estructura de mis productos químicos). La razón por la que lo hago estocásticamente es para poder intercalar los procesos de reacción química con la dispersión de la distancia, y simular un químico que cambia gradualmente de forma a medida que ocurre la reacción (en lugar de cambiar de forma instantáneamente).
El self en esta función es un objeto que representa un producto químico. Los nodos en self.node_distances.keys() son los átomos que componen el producto químico. Los nodos en self.node_distances[node_x].keys() son nodos del químico y potencialmente nodos de cualquier químico al que el producto químico está unido (y reacciona).
Actualización:
intenté reemplazar todas las instancias de node_x == node_y con node_x is node_y (según el comentario de @Sven Marnach), pero se desaceleró cosas! (¡No esperaba eso!) Mi perfil original tomó 807.234s para ejecutarse, pero con esta modificación aumentó a 895.895. Disculpa, estaba haciendo el perfil equivocado Estaba usando line_by_line, que (en mi código) tenía demasiada variación (esa diferencia de ~ 90 segundos estaba en el ruido). Al perfilarlo correctamente, is es infinitamente más rápido que ==. Usando CProfile, mi código con == tomó 34.394s, pero con is, tomó 33.535s (que puedo confirmar que está fuera del ruido).
Actualización: Las bibliotecas existentes
estoy seguro de si habrá una biblioteca existente que puede hacer lo que quiera, ya que mis necesidades son inusuales: necesito para calcular la ruta más corta longitudes entre todos los pares de nodos en un gráfico ponderado, no dirigido. Solo me importan las longitudes de ruta que sean inferiores a un valor umbral. Después de calcular las longitudes de las rutas, realizo un pequeño cambio en la topología de la red (agregando o eliminando un borde), y luego quiero volver a calcular las longitudes de la ruta. Mis gráficos son enormes en comparación con el valor umbral (desde un nodo dado, la mayoría del gráfico está más alejado que el umbral), por lo que los cambios de topología no afectan a la mayoría de las longitudes de ruta más cortas. Esta es la razón por la que estoy usando el algoritmo de enrutamiento: porque esto propaga la información de cambio de topología a través de la estructura del gráfico, por lo que puedo dejar de propagarla cuando se haya ido más allá del umbral. es decir, no necesito volver a calcular todas las rutas cada vez. Puedo usar la información de ruta anterior (desde antes del cambio de topología) para acelerar el cálculo. Esta es la razón por la que creo que mi algoritmo será más rápido que cualquier implementación de la biblioteca de algoritmos de ruta más corta. Nunca he visto algoritmos de enrutamiento utilizados fuera de enrutar paquetes a través de redes físicas (pero si alguien tiene, entonces estaría interesado).
NetworkX fue sugerido por @Thomas K. Tiene lots of algorithms para calcular las rutas más cortas. Tiene un algoritmo para calcular el all-pairs shortest path lengths con un punto de corte (que es lo que quiero), pero solo funciona en gráficos sin ponderar (los míos son ponderados). Desafortunadamente, su algorithms for weighted graphs no permite el uso de un límite (lo que puede hacer que se vuelvan lentos para mis gráficos). Y ninguno de sus algoritmos parece ser compatible con el uso de rutas precalculadas en una red muy similar (es decir, el material de enrutamiento).
igraph es otra biblioteca de gráfico que conozco, pero al mirar its documentation, no encuentro nada sobre las rutas más cortas. Pero me podría haber perdido, su documentación no parece muy completa.
NumPy puede ser posible, gracias al comentario de @ 9000. Puedo almacenar mi matriz dispersa en una matriz NumPy si asigno un entero único a cada instancia de mis nodos. Luego puedo indexar una matriz NumPy con enteros en lugar de instancias de nodo. También necesitaré dos matrices NumPy: una para las distancias y otra para las referencias de "next_node". Esto podría ser más rápido que usar diccionarios de Python (aún no lo sé).
¿Alguien sabe de alguna otra biblioteca que pueda ser útil?
Actualización: Uso de memoria
Estoy utilizando Windows (XP), asi que aquí hay algo de información sobre el uso de memoria, desde Process Explorer. El uso de la CPU es del 50% porque tengo una máquina de doble núcleo.
Mi programa no se ejecuta sin memoria RAM y comienza a golpear el intercambio. Puede ver eso a partir de los números, y del gráfico IO que no tiene ninguna actividad. Los picos en el gráfico IO son donde el programa imprime en la pantalla para decir cómo está.
Sin embargo, mi programa no siga usando más y más memoria RAM con el tiempo, lo que probablemente no es una buena cosa (pero no está consumiendo la cantidad de RAM en general, por lo que no me di cuenta el aumento hasta el momento).
Y la distancia entre los picos en el gráfico IO aumenta con el tiempo. Esto es malo: mi programa imprime en la pantalla cada 100.000 iteraciones, lo que significa que cada iteración tarda más en ejecutarse a medida que pasa el tiempo ... Lo he confirmado haciendo un largo recorrido de mi programa y midiendo el tiempo transcurrido entre declaraciones de impresión (el tiempo entre cada 10.000 iteraciones del programa). Esto debería ser constante, pero como se puede ver en el gráfico, aumenta linealmente ... entonces algo está ahí arriba. (El ruido en este gráfico es porque mi programa utiliza una gran cantidad de números aleatorios, por lo que el tiempo para cada iteración varía.)
Después de mi programa ha estado funcionando durante mucho tiempo, el uso de la memoria es el siguiente (por lo que definitivamente no quedarse sin RAM):
Ojalá todas las preguntas tuvieran este tipo de contenido, me entristece no poder ayudarte. – Leigh
¿Has considerado la posibilidad de paralelizar tu algoritmo? Si no puede hacer los cálculos centrales más rápido, aún podrá acelerarlo si tiene múltiples núcleos disponibles. – samtregar
En cuanto a las comparaciones, le desconcierta: el operador '==' realmente llama al método '__eq __()' del objeto comparado. Si todo lo que quiere saber es identidad de objeto, use 'is' en su lugar, esto será considerablemente más rápido. –