recorrer - Optimizar el código de acceso del diccionario de Python
lista de diccionarios python (5)
Pregunta:
He perfilado mi programa Python hasta la muerte, y hay una función que ralentiza todo. 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 puedas dar sentido a mi código! Gracias de antemano por cualquier ayuda.
Mi código:
Esta es la función ofensiva, perfilada mediante line_profiler y 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 desproporcionada.
Consideré 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 objetos); 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 sobre el 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 pueda ejecutar, pero esta función está atada en 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():
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)
Explicación de mi código:
Esta función mantiene una matriz de distancia dispersa que representa la distancia de red (suma de los pesos de borde en la ruta más corta) entre los nodos en una red (muy grande). Trabajar con la tabla completa y usar el algoritmo de Floyd-Warshall 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 un protocolo de enrutamiento de vector de distancia : 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 los cambios de topología, dos nodos que estaban muy separados (o no están conectados en absoluto) pueden volverse cercanos. 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 se modifican continuamente externamente a esta función, mediante 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 protocolo de enrutamiento vectorial de distancia . Dado un nodo, node_a , la función se asegura de que los vecinos de node_a estén correctamente en la matriz de distancia (la topología cambia). La función luego envía la tabla de enrutamiento de node_a a todos los vecinos inmediatos de node_a en la red. Integra la tabla de enrutamiento de 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 enrutamiento desde la última actualización. En cada iteración de mi algoritmo, se elige un subconjunto aleatorio de estos nodos y se llama a propagate_distances_node() sobre ellos. 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 vuelve vacío.
Las partes de "distancias de afinidad" ( add_affinityDistance y del_affinityDistance ) son un caché de una (pequeña) del_affinityDistance 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 protocolo de enrutamiento de vector de distancia es la manera 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 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 químico está ligado (y reacciona).
Actualizar:
Intenté reemplazar cada instancia de node_x == node_y con node_x is node_y (según el comentario de @Sven Marnach), pero ralentizó las cosas! (¡No esperaba eso!) Mi perfil original tomó 807.234s para ejecutarse, pero con esta modificación aumentó a 895.895. Lo siento, estaba haciendo el perfil incorrecto! 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, 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: bibliotecas existentes
No estoy seguro de si habrá una biblioteca existente que pueda hacer lo que quiero, ya que mis requisitos son inusuales: necesito calcular las longitudes de ruta más cortas 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 muchos algoritmos para calcular las rutas más cortas. Tiene un algoritmo para calcular las longitudes de camino más cortas de todos los pares con un límite (que es lo que quiero), pero solo funciona en gráficos no ponderados (los míos son ponderados). Desafortunadamente, sus algoritmos para gráficos ponderados no permiten el uso de un punto de corte (lo que puede hacer que sean lentos para mis gráficos). Y ninguno de sus algoritmos parece apoyar el uso de rutas precalculadas en una red muy similar (es decir, el material de enrutamiento).
igraph es otra biblioteca de gráficos que conozco, pero mirando su documentación , no puedo encontrar nada acerca de las rutas más cortas. Pero me podría haber perdido, su documentación no parece muy completa.
NumPy podría 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 ejecutando Windows (XP), así que aquí hay información sobre el uso de la 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 queda sin 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 sigue consumiendo más y más RAM a lo largo del tiempo, lo que probablemente no sea bueno (pero no está consumiendo mucha RAM en general, por lo que no noté el aumento hasta ahora).
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 se debe a que mi programa usa muchos números aleatorios, por lo que el tiempo para cada iteración varía).
Después de que mi programa ha estado funcionando durante mucho tiempo, el uso de la memoria se ve así (por lo que definitivamente no se está quedando sin RAM):
Esto requeriría una buena cantidad de trabajo, pero ... podría considerar usar Floyd-Warshall ejecutándose en una GPU. Se ha trabajado mucho para lograr que Floyd-Warshall funcione de manera muy eficiente en una GPU. Una rápida búsqueda en Google produce:
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://www.gpucomputing.net/?q=node/1203
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter43.html
A pesar de que, como se implementó en Python, Floyd-Warshall fue más lento en un orden de magnitud, una buena versión de GPU en una poderosa GPU aún podría superar significativamente a su nuevo código Python.
Aquí hay una anécdota. Tuve una pieza de código breve, simple y de uso intensivo de cómputo que hizo algo similar a una acumulación de datos. En Python, optimizado como pude obtenerlo, tomó ~ 7s en un veloz i7. Luego escribí una versión de GPU completamente no optimizada; tomó ~ 0.002s en una Nvidia GTX 480. YMMV, pero para cualquier cosa significativamente paralela, la GPU es probable que sea un ganador a largo plazo, y dado que es un algoritmo bien estudiado, debería ser capaz de utilizar el código altamente afinado existente .
Para el puente Python / GPU, recomendaría PyCUDA o PyOpenCL.
No veo nada incorrecto con su código en cuanto a rendimiento (sin intentar asimilar el algoritmo), solo está siendo golpeado por la gran cantidad de iteraciones. ¡Partes de tu código se ejecutan 40 millones de veces!
Observe cómo el 80% del tiempo se gasta en el 20% de su código, y esas son las 13 líneas que se ejecutan más de 24 millones de veces. Por cierto, con este código se proporciona una gran ilustración del principio de Pareto (o "el 20% de los bebedores de cerveza beben el 80% de la cerveza").
Lo primero es lo primero : ¿has probado Psycho ? Es un compilador JIT que puede acelerar mucho tu código, teniendo en cuenta la gran cantidad de iteraciones, por ejemplo, de 4x-5x, y todo lo que tienes que hacer (después de descargar e instalar, por supuesto) es insertar este fragmento en el comenzando:
import psyco
psyco.full()
Es por eso que me gustó Psycho y lo usé también en GCJ, donde el tiempo es esencial: nada para codificar, nada para equivocarse y un impulso repentino de 2 líneas agregadas.
Volvemos a la recolección de liendres (que cambia como reemplazar == con is etc, debido a la pequeña mejora del% de tiempo). Aquí están las 13 líneas "en falta":
Line # Hits Time Per Hit % Time Line Contents
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
386 42076729 184216680432 4378.1 7.6 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
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)
413 41838114 180297579789 4309.4 7.4 if(distance_b_c > cutoff_distance):
363 41244762 172425596985 4180.5 7.1 if(node_after_b == node_a):
389 41564609 172040284089 4139.1 7.1 if(node_c == node_b): # a-b path
388 41564609 171150289218 4117.7 7.1 node_b_update = False
391 41052489 169406668962 4126.6 7 elif(node_after_a == node_b): # a-b-a-b path
405 41564609 164585250189 3959.7 6.8 if node_b_update:
394 24004846 103404357180 4307.6 4.3 (distance_b_c, node_after_b) = node_b_distances[node_c]
395 24004846 102717271836 4279 4.2 if(node_after_b != node_a): # b doesn''t already go to a first
393 24801082 101577038778 4095.7 4.2 elif(node_c in node_b_distances): # b can already get to c
A) Además de las líneas que mencionas, observo que # 388 tiene un tiempo relativamente alto cuando es trivial, todo lo que hace es node_b_update = False . Ah, pero espera, ¡cada vez que se ejecuta, False se busca en el ámbito global! Para evitar eso, asigne F, T = False, True en el comienzo del método y reemplace los usos posteriores de False y True con los locales F y T Esto debería disminuir el tiempo total, aunque por poco (3%?).
B) Noto que la condición en # 389 ocurrió "solo" 512,120 veces (basado en el número de ejecuciones del # 390) contra la condición en el # 391 con 16,251,407. Como no hay dependencia, tiene sentido invertir el orden de esos controles, debido al "corte" temprano que debería dar poco impulso (¿2%?). No estoy seguro si evitar las declaraciones de pass conjunto ayudará, pero si no perjudica la legibilidad:
if (node_after_a is not node_b) and (node_c is not node_b):
# neither a-b-a-b nor a-b path
if (node_c in node_b_distances): # b can already get to c
(distance_b_c, node_after_b) = node_b_distances[node_c]
if (node_after_b is not node_a): # b doesn''t already go to a first
distance_b_a_c = neighbour_distance_b_a + distance_a_c
if (distance_b_a_c < distance_b_c): # quicker to go via a
node_b_update = T
else: # b can''t already get to c
distance_b_a_c = neighbour_distance_b_a + distance_a_c
if (distance_b_a_c < cutoff_distance): # not too for to go
node_b_update = T
C) Me acabo de dar cuenta de que estás usando try-except en un caso (# 365-367) solo necesitas el valor predeterminado de un diccionario. Intenta usar en .get(key, defaultVal) lugar .get(key, defaultVal) o crea tus diccionarios con collections.defaultdict(itertools.repeat(float(''+inf''))) . Usar try-except tiene su precio - ver # 365 informes 3.5% del tiempo, eso es configurar marcos de pila y otras cosas.
D) Evite el acceso indexado (ya sea con obj . Field u obj [ idx ] ) cuando sea posible. Por ejemplo, veo que usas self.node_distances[node_a] en varios lugares (# 336, 339, 346, 366, 386), lo que significa que para cada uso, la indexación se usa dos veces (una vez para . Y una para [] ) - y eso se vuelve costoso cuando se ejecuta decenas de millones de veces. Me parece que puede hacer en el método que comienza con node_a_distances = self.node_distances[node_a] y luego usar eso más adelante.
node_after_b == node_a intentará llamar a node_after_b.__eq__(node_a) :
>>> class B(object):
... def __eq__(self, other):
... print "B.__eq__()"
... return False
...
>>> class A(object):
... def __eq__(self, other):
... print "A.__eq__()"
... return False
...
>>> a = A()
>>> b = B()
>>> a == b
A.__eq__()
False
>>> b == a
B.__eq__()
False
>>>
Intente anular el Node.__eq__() con una versión optimizada antes de recurrir a C.
ACTUALIZAR
Hice este pequeño experimento (Python 2.6.6):
#!/usr/bin/env python
# test.py
class A(object):
def __init__(self, id):
self.id = id
class B(A):
def __eq__(self, other):
return self.id == other.id
@profile
def main():
list_a = []
list_b = []
for x in range(100000):
list_a.append(A(x))
list_b.append(B(x))
ob_a = A(1)
ob_b = B(1)
for ob in list_a:
if ob == ob_a:
x = True
if ob is ob_a:
x = True
if ob.id == ob_a.id:
x = True
if ob.id == 1:
x = True
for ob in list_b:
if ob == ob_b:
x = True
if ob is ob_b:
x = True
if ob.id == ob_b.id:
x = True
if ob.id == 1:
x = True
if __name__ == ''__main__'':
main()
Resultados:
Timer unit: 1e-06 s
File: test.py Function: main at line 10 Total time: 5.52964 s
Line # Hits Time Per Hit % Time Line Contents
==============================================================
10 @profile
11 def main():
12 1 5 5.0 0.0 list_a = []
13 1 3 3.0 0.0 list_b = []
14 100001 360677 3.6 6.5 for x in range(100000):
15 100000 763593 7.6 13.8 list_a.append(A(x))
16 100000 924822 9.2 16.7 list_b.append(B(x))
17
18 1 14 14.0 0.0 ob_a = A(1)
19 1 5 5.0 0.0 ob_b = B(1)
20 100001 500454 5.0 9.1 for ob in list_a:
21 100000 267252 2.7 4.8 if ob == ob_a:
22 x = True
23 100000 259075 2.6 4.7 if ob is ob_a:
24 x = True
25 100000 539683 5.4 9.8 if ob.id == ob_a.id:
26 1 3 3.0 0.0 x = True
27 100000 271519 2.7 4.9 if ob.id == 1:
28 1 3 3.0 0.0 x = True
29 100001 296736 3.0 5.4 for ob in list_b:
30 100000 472204 4.7 8.5 if ob == ob_b:
31 1 4 4.0 0.0 x = True
32 100000 283165 2.8 5.1 if ob is ob_b:
33 x = True
34 100000 298839 3.0 5.4 if ob.id == ob_b.id:
35 1 3 3.0 0.0 x = True
36 100000 291576 2.9 5.3 if ob.id == 1:
37 1 3 3.0 0.0 x = True
Estaba muy sorprendido:
- El acceso "punto" (ob.property) parece ser muy costoso (línea 25 frente a línea 27).
- no había mucha diferencia entre is y ''=='', al menos para objetos simples
Luego probé con objetos más complejos y los resultados son consistentes con el primer experimento.
¿Estás intercambiando mucho? Si su conjunto de datos es tan grande que no cabe en la memoria RAM disponible, supongo que puede experimentar algún tipo de conflicto de E / S relacionado con las recuperaciones de memoria virtual.
¿Estás ejecutando Linux? Si es así, ¿podría publicar un vmstat de su máquina mientras ejecuta su programa? Envíenos el resultado de algo como:
vmstat 10 100
¡Buena suerte!
ACTUALIZACIÓN (de los comentarios de OP)
Intenté jugar con sys.setcheckinterval y habilitar / deshabilitar el GC. El fundamento es que, para este caso particular (gran cantidad de instancias), la verificación de recuento de referencias GC por defecto es algo costosa y su intervalo predeterminado es demasiado frecuente.
Sí, anteriormente había jugado con sys.setcheckinterval. Lo cambié a 1000 (de su valor predeterminado de 100), pero no hizo ninguna diferencia medible. Desactivar la recolección de basura ha ayudado, gracias. Esta ha sido la aceleración más grande hasta el momento, ahorrando aproximadamente un 20% (171 minutos durante toda la ejecución, hasta 135 minutos). No estoy seguro de cuáles son las barras de error, pero debe ser un aumento estadísticamente significativo. - Adam Nellis 9 de febrero a las 15:10
Mi conjetura:
Creo que el Python GC se basa en el recuento de referencias. De vez en cuando comprobará el recuento de referencias para cada instancia; ya que está atravesando estas enormes estructuras en memoria, en su caso particular la frecuencia por defecto del GC (¿1000 ciclos?) es demasiado frecuente, una gran pérdida. - Atentamente, 10 de febrero a las 2:06
I would have posted this as an update to my question, but only allows 30000 characters in questions, so I''m posting this as an answer.
Update: My best optimisations so far
I''ve taken on board people''s suggestions, and now my code runs about 21% faster than before, which is good - thanks everyone!
This is the best I''ve managed to do so far. I''ve replaced all the == tests with is for nodes, disabled garbage collection and re-written the big if statement part at Line 388, in line with @Nas Banov''s suggestions. I added in the well-known try/except trick for avoiding tests (line 390 - to remove the test node_c in node_b_distances ), which helped loads, since it hardly ever throws the exception. I tried switching lines 391 and 392 around, and assigning node_b_distances[node_c] to a variable, but this way was the quickest.
However, I still haven''t tracked down the memory leak yet (see graph in my question). But I think this might be in a different part of my code (that I haven''t posted here). If I can fix the memory leak, then this program will run quickly enough for me to use :)
Timer unit: 3.33366e-10 s
File: routing_distances.py
Function: propagate_distances_node at line 328
Total time: 760.74 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 791349 4158169713 5254.5 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
334 550522 2331886050 4235.8 0.1 use_neighbour_link = False
335
336 550522 2935995237 5333.1 0.1 if(node_b not in self.node_distances[node_a]): # a doesn''t know distance to b
337 15931 68829156 4320.5 0.0 use_neighbour_link = True
338 else: # a does know distance to b
339 534591 2728134153 5103.2 0.1 (node_distance_b_a, next_node) = self.node_distances[node_a][node_b]
340 534591 2376374859 4445.2 0.1 if(node_distance_b_a > neighbour_distance_b_a): # neighbour distance is shorter
341 78 347355 4453.3 0.0 use_neighbour_link = True
342 534513 3145889079 5885.5 0.1 elif((None is next_node) and (float(''+inf'') == neighbour_distance_b_a)): # direct route that has just broken
343 74 327600 4427.0 0.0 use_neighbour_link = True
344
345 550522 2414669022 4386.1 0.1 if(use_neighbour_link):
346 16083 81850626 5089.3 0.0 self.node_distances[node_a][node_b] = (neighbour_distance_b_a, None)
347 16083 87064200 5413.4 0.0 self.nodes_changed.add(node_a)
348
349 ## Affinity distances update
350 16083 86580603 5383.4 0.0 if((node_a.type == Atom.BINDING_SITE) and (node_b.type == Atom.BINDING_SITE)):
351 234 6656868 28448.2 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 791349 4034651958 5098.4 0.2 for (node_b, neighbour_distance_b_a) in self.neighbours[node_a].iteritems():
355 550522 2392248546 4345.4 0.1 node_b_changed = False
356
357 # b integrates a''s distance table with its own
358 550522 2520330696 4578.1 0.1 node_b_chemical = node_b.chemical
359 550522 2734341975 4966.8 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 46679347 222161837193 4759.3 9.7 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 46128825 211963639122 4595.0 9.3 if(node_after_b is node_a):
364
365 18677439 79225517916 4241.8 3.5 try:
366 18677439 101527287264 5435.8 4.4 distance_b_a_c = neighbour_distance_b_a + self.node_distances[node_a][node_c][0]
367 181510 985441680 5429.1 0.0 except KeyError:
368 181510 1166118921 6424.5 0.1 distance_b_a_c = float(''+inf'')
369
370 18677439 89626381965 4798.6 3.9 if(distance_b_c != distance_b_a_c): # a''s distance to c has changed
371 692131 3352970709 4844.4 0.1 node_b_distances[node_c] = (distance_b_a_c, node_a)
372 692131 3066946866 4431.2 0.1 node_b_changed = True
373
374 ## Affinity distances update
375 692131 3808548270 5502.6 0.2 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
376 96794 1655818011 17106.6 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 18677439 88838493705 4756.5 3.9 if(distance_b_a_c > distance_b_c):
381 #for (node, neighbour_distance) in node_b_chemical.neighbours[node_b].iteritems():
382 1656796 7949850642 4798.3 0.3 for node in node_b_chemical.neighbours[node_b]:
383 1172486 6307264854 5379.4 0.3 node.chemical.nodes_changed.add(node)
384
385 # Look for routes from a to c that are quicker than ones b knows already
386 46999631 227198060532 4834.0 10.0 for node_c, (distance_a_c, node_after_a) in self.node_distances[node_a].iteritems():
387
388 46449109 218024862372 4693.8 9.6 if((node_after_a is not node_b) and # not a-b-a-b path
389 28049321 126269403795 4501.7 5.5 (node_c is not node_b)): # not a-b path
390 27768341 121588366824 4378.7 5.3 try: # Assume node_c in node_b_distances (''try'' block will raise KeyError if not)
391 27768341 159413637753 5740.8 7.0 if((node_b_distances[node_c][1] is not node_a) and # b doesn''t already go to a first
392 8462467 51890478453 6131.8 2.3 ((neighbour_distance_b_a + distance_a_c) < node_b_distances[node_c][0])):
393
394 # Found a route
395 224593 1168129548 5201.1 0.1 node_b_distances[node_c] = (neighbour_distance_b_a + distance_a_c, node_a)
396 ## Affinity distances update
397 224593 1274631354 5675.3 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
398 32108 551523249 17177.1 0.0 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
399 224593 1165878108 5191.1 0.1 node_b_changed = True
400
401 809945 4449080808 5493.1 0.2 except KeyError:
402 # b can''t already get to c (node_c not in node_b_distances)
403 809945 4208032422 5195.5 0.2 if((neighbour_distance_b_a + distance_a_c) < cutoff_distance): # not too for to go
404
405 # These lines of code copied, for efficiency
406 # (most of the time, the ''try'' block succeeds, so don''t bother testing for (node_c in node_b_distances))
407 # Found a route
408 587726 3162939543 5381.7 0.1 node_b_distances[node_c] = (neighbour_distance_b_a + distance_a_c, node_a)
409 ## Affinity distances update
410 587726 3363869061 5723.5 0.1 if((node_b.type == Atom.BINDING_SITE) and (node_c.type == Atom.BINDING_SITE)):
411 71659 1258910784 17568.1 0.1 node_b_chemical.add_affinityDistance(node_b, node_c, self.chemistry.affinity(node_b.data, node_c.data))
412 587726 2706161481 4604.5 0.1 node_b_changed = True
413
414
415
416 # If any of node b''s rows have exceeded the cutoff distance, then remove them
417 47267073 239847142446 5074.3 10.5 for node_c, (distance_b_c, node_after_b) in node_b_distances.items(): # Can''t use iteritems() here, as deleting from the dictionary
418 46716551 242694352980 5195.0 10.6 if(distance_b_c > cutoff_distance):
419 200755 967443975 4819.0 0.0 del node_b_distances[node_c]
420 200755 930470616 4634.9 0.0 node_b_changed = True
421
422 ## Affinity distances update
423 200755 4717125063 23496.9 0.2 node_b_chemical.del_affinityDistance(node_b, node_c)
424
425 # If we''ve modified node_b''s distance table, tell its chemical to update accordingly
426 550522 2684634615 4876.5 0.1 if(node_b_changed):
427 235034 1383213780 5885.2 0.1 node_b_chemical.nodes_changed.add(node_b)
428
429 # Remove any neighbours that have infinite distance (have just unbound)
430 ## TODO: not sure what difference it makes to do this here rather than above (after updating self.node_distances for neighbours)
431 ## but doing it above seems to break the walker''s movement
432 791349 4367879451 5519.5 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
433 550522 2968919613 5392.9 0.1 if(neighbour_distance_b_a > cutoff_distance):
434 148 775638 5240.8 0.0 del self.neighbours[node_a][node_b]
435
436 ## Affinity distances update
437 148 2096343 14164.5 0.0 self.del_affinityDistance(node_a, node_b)