resueltos recorrer lista elementos ejercicios diccionarios diccionario dentro anidados agregar python optimization dictionary sparse-matrix

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

¿Has considerado Pyrex / Cython ?

Compila python a C y luego a .pyd automáticamente, por lo que puede acelerar un poco las cosas sin mucho trabajo.

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://my.safaribooksonline.com/book/programming/graphics/9780321545411/gpu-computing-for-protein-structure-prediction/ch43lev1sec2#X2ludGVybmFsX0ZsYXNoUmVhZGVyP3htbGlkPTk3ODAzMjE1NDU0MTEvNDg3

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)