Оптимизация Python код доступа словарь

Question

Вопрос:

Я профилированного свою программу Python до смерти, и есть одна функция, которая замедляет все вниз. Он сильно использует словари Python, поэтому я, возможно, не использовал их наилучшим образом. Если я не могу заставить его работать быстрее, мне придется перезаписать его на C++, так есть ли кто-нибудь, кто может помочь мне оптимизировать его в Python?

Надеюсь, я дал правильное объяснение и что вы можете понять смысл моего кода! Заранее благодарю за любую помощь.

Мой код:

Это функция обижая, профилированный с помощью line_profiler and kernprof. Я запускаю Python 2.7

Я особенно озадачен такими вещами, как строки 363, 389 и 405, где заявление if с сопоставлением двух переменных, кажется, занимает чрезмерное количество времени.

Я рассмотрел использование NumPy (так как он имеет разреженные матрицы), но я не думаю, что это уместно, потому что: (1) Я не индексирую свою матрицу с помощью целых чисел (я использую экземпляры объектов); и (2) Я не храню простые типы данных в матрице (я храню кортежи float и экземпляр объекта). Но я готов быть убежденным о NumPy. Если кто-нибудь знает о разреженной производительности матрицы NumPy и хэш-таблицах Python, мне было бы интересно.

Извините, я не привел простой пример того, что вы можете запускать, но эта функция связана в гораздо большем проекте, и я не мог понять, как настроить простой пример для тестирования, не давая вам половина моей базы кода!

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) 

Объяснение моего кода:

Эта функция поддерживает разреженную матрицу расстояния, представляющую сетевое расстояние (сумма весов ребер на кратчайшем пути) между узлами в (очень большой) сети. Работа с полной таблицей и использование Floyd-Warshall algorithm будет очень медленным. (Я пробовал это сначала, и он был на порядок медленнее, чем текущая версия.) Таким образом, мой код использует разреженную матрицу для представления пороговой версии полной матрицы расстояния (любые пути с расстоянием более 200 единиц игнорируются). Сетевая тополяция меняется со временем, поэтому эта матрица расстояний требует обновления со временем. Для этого я использую грубую реализацию distance-vector routing protocol: каждый узел в сети знает расстояние друг к другу и следующий узел на пути. Когда происходит изменение топологии, узел (узлы), связанные с этим изменением, обновляют таблицу (ы) расстояния соответственно и сообщают своим ближайшим соседям. Информация распространяется по сети посредством узлов, отправляющих свои таблицы расстояний своим соседям, которые обновляют свои таблицы расстояний и распространяют их на своих соседей.

Существует объект, представляющий матрицу расстояний: self.node_distances. Это словарь, сопоставляющий узлы с таблицами маршрутизации. Узел - это объект, который я определил. Таблица маршрутизации - это словарь, сопоставляющий узлы с кортежами (distance, next_node). Расстояние - это расстояние графика от node_a до node_b, а next_node - это сосед узла_a, с которым вы должны идти первым, на пути между node_a и node_b. Next_node of None указывает, что node_a и node_b являются соседями графа.Например, образец расстоянии матрицы может быть:

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

Из-за изменения топологии, двух узлов, которые были далеко друг от друга (или не подключен вообще) может стать близко. Когда это произойдет, записи добавляются в эту матрицу. Из-за порога, два узла могут стать слишком далеко друг от друга, чтобы заботиться. Когда это происходит, записи удаляются из этой матрицы.

Матрица self.neighbours похожа на self.node_distances, но содержит информацию о прямых ссылках (краях) в сети. self.neighbours постоянно модифицируется внешне этой функцией химической реакцией. Именно здесь происходят изменения в топологии сети.

Фактическая функция, с которой у меня возникают проблемы: propagate_distances_node() выполняет один шаг distance-vector routing protocol. При заданном узле node_a функция гарантирует, что соседние соты node_a правильно расположены в матрице расстояний (изменения топологии). Затем функция отправляет таблицу маршрутизации node_a всем ближайшим соседямв сети. Он объединяет таблицу маршрутизации node_a с собственной таблицей маршрутизации каждого соседа.

В остальной части моей программы функция propagate_distances_node() вызывается многократно, пока матрица расстояний не сходится. Поддерживается набор, self.nodes_changed, узлов, которые изменили свою таблицу маршрутизации с момента последнего обновления. На каждой итерации моего алгоритма выбирается случайное подмножество этих узлов и на них вызывается propagate_distances_node(). Это означает, что узлы распределяют свои таблицы маршрутизации асинхронно и стохастически. Этот алгоритм сходится на истинной матрице расстояния, когда набор self.nodes_changed становится пустым.

Элементы «расстояния близости» (add_affinityDistance и del_affinityDistance) являются кешем (малой) подматрицы матрицы расстояния, которая используется другой частью программы.

Причина, по которой я делаю это, заключается в том, что я имитирую вычислительные аналоги химических веществ, участвующих в реакциях, как часть моей докторской диссертации. «Химический» - это график «атомов» (узлов на графике). Два химических связывания вместе моделируются, так как их два графика соединяются новыми краями. Химическая реакция происходит (сложным процессом, который здесь не уместен), изменяя топологию графика. Но то, что происходит в реакции, зависит от того, насколько сильно разные атомы составляют химические вещества. Поэтому для каждого атома в симуляции я хочу знать, к каким другим атомам он близок. Редкая, пороговая матрица расстояний является наиболее эффективным способом хранения этой информации. Поскольку топология сети изменяется по мере того, как происходит реакция, мне нужно обновить матрицу. A distance-vector routing protocol - это самый быстрый способ сделать это. Мне не нужен более сложный протокол маршрутизации, потому что в моем конкретном приложении такие вещи, как петли маршрутизации, не происходят (из-за того, как структурируются мои химические вещества). Причина, по которой я делаю это стохастически, заключается в том, что я могу взаимодействовать с процессами химической реакции с распространением расстояния и имитировать химическую, постепенно меняющуюся форму с течением времени, когда происходит реакция (а не мгновенно менять форму).

self в этой функции представляет собой объект, представляющий химическое вещество. Узлами в self.node_distances.keys() являются атомы, которые составляют химическое вещество. Узлы в self.node_distances[node_x].keys() являются узлами химического вещества и потенциальными узлами любых химических веществ, к которым химическое вещество связано (и реагирует с).

Update:

Я попытался заменить каждый экземпляр node_x == node_y с node_x is node_y (в соответствии с комментарием @Sven Marnach в), но замедляло работу! (Я этого не ожидал!) Мой первоначальный профиль занял 807.234s для запуска, но с этой модификацией он увеличился до 895.895s. Извините, я неправильно делал профилирование! Я использовал line_by_line, который (по моему коду) имел слишком большую дисперсию (разница в ~ 90 секунд была в шуме). При профилировании его должным образом is является безусловным быстрее, чем ==. Используя CProfile, мой код с == занял 34.394s, но с is потребовалось 33.535s (что я могу подтвердить, это из-за шума).

Update: Существующих библиотеки

Я не уверен, будет ли там быть существующей библиотека, которая может делать то, что я хочу, так как мои требования необычны: мне нужно вычислить кратчайший путь длины между всеми парами узлов в взвешенном неориентированном графе. Меня интересуют только длины пути, которые ниже порогового значения. После вычисления длины пути я делаю небольшое изменение в топологии сети (добавление или удаление края), а затем я хочу повторно вычислить длину пути. Мои графики огромны по сравнению с пороговым значением (от данного узла, большая часть графика находится дальше, чем порог), поэтому изменения топологии не влияют на большинство длин кратчайшего пути. Вот почему я использую алгоритм маршрутизации: потому что это распространяет информацию об изменении топологии через структуру графика, поэтому я могу остановить ее распространение, когда она ушла дальше порога. то есть мне не нужно повторно вычислять все пути каждый раз. Я могу использовать предыдущую информацию о пути (до изменения топологии), чтобы ускорить вычисление. Вот почему я считаю, что мой алгоритм будет быстрее, чем любые реализации библиотек алгоритмов кратчайшего пути. Я никогда не видел алгоритмы маршрутизации, используемые за пределами фактически маршрутизирующих пакетов через физические сети (но если кто-то есть, то мне было бы интересно).

NetworkX было предложено @Thomas K. У этого lots of algorithms для расчета кратчайших путей. У этого есть алгоритм для вычисления all-pairs shortest path lengths с отсечкой (это то, что я хочу), но он работает только на невзвешенных графиках (мои взвешиваются). К сожалению, его algorithms for weighted graphs не позволяют использовать отсечку (что может замедлить работу моих графиков). И ни один из его алгоритмов не поддерживает использование предварительно рассчитанных путей в очень похожей сети (т. Е. Материал маршрутизации).

igraph - это еще одна библиотека графов, которую я знаю, но смотрю на its documentation, я не могу найти ничего о кратчайших дорожках. Но я, возможно, пропустил это - его документация не кажется очень всеобъемлющей.

NumPy возможно, благодаря комментарию @ 9000. Я могу сохранить мою разреженную матрицу в массиве NumPy, если я назначу уникальное целое число для каждого экземпляра моих узлов. Затем я могу индексировать массив NumPy с целыми числами вместо экземпляров узлов. Мне также понадобятся два массива NumPy: один для расстояний и один для ссылок «next_node». Это может быть быстрее, чем использование словарей Python (пока я еще не знаю).

Кто-нибудь знает какие-либо другие библиотеки, которые могут быть полезны?

Обновление: Использование памяти

Я бегу Windows (XP), так вот некоторая информация об использовании памяти, из Process Explorer. Использование процессора составляет 50%, потому что у меня двухъядерная машина.

Моя программа не запускается из памяти и начинают дубасить подкачки. Вы можете видеть, что из чисел и из графика ввода-вывода не имеет никакой активности. Шипы на графике ввода-вывода - это то место, где программа печатает на экране, чтобы сказать, как это делается.

Тем не менее, моя программа продолжает использовать все больше и больше ОЗУ с течением времени, что, вероятно, не очень хорошо (но он не использует много оперативной памяти, поэтому я не заметил увеличения до сих пор).

И расстояние между шипами на графике ввода-вывода увеличивается с течением времени. Это плохо - моя программа выводит на экран каждые 100 000 итераций, поэтому это означает, что каждая итерация занимает больше времени для выполнения с течением времени ... Я подтвердил это, выполняя длинную программу и измеряя время между print (время между каждыми 10 000 итераций программы). Это должно быть постоянным, но, как видно из графика, оно линейно растет ... так что что-то там. (Шум на этом графике, потому что моя программа использует много случайных числа, так что время для каждой итерации изменяется.)

После моей программы работает уже в течение длительного времени, использование памяти выглядит следующим образом (так что это определенно не хватает оперативной памяти):

Answer 1

node_after_b == node_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 
>>> 

Попытка переопределить Node.__eq__() с оптимизированной версией, прежде чем прибегать к C.

UPDATE

Я сделал этот небольшой эксперимент (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() 

Результаты:

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 

Я был очень удивлен:

• «dot» access (ob.property) представляется очень дорогим (строка 25 по строке 27).
• не было большой разницы между есть и «==», по крайней мере, для простых объектов

Затем я попытался с более сложными объектами и результаты согласуются с первым экспериментом.

Вы меняете местами? Если ваш набор данных настолько велик, что он не подходит для доступной оперативной памяти, я думаю, вы можете столкнуться с каким-либо конфликтом ввода-вывода, связанным с извлечением виртуальной памяти.

Вы используете Linux? Если да, можете ли вы опубликовать vmstat своей машины во время запуска вашей программы? Пришлите нам вывод чего-то вроде:

vmstat 10 100 

Удачи!

UPDATE (от комментариев по OP)

Я мотивационные играть с sys.setcheckinterval и включить/отключить GC. Обоснование заключается в том, что для этого конкретного случая (огромное количество экземпляров) проверка счетчика ссылок GC по умолчанию несколько дорогая, и его интервал по умолчанию слишком далеко.

Да, я ранее играл с sys.setcheckinterval. Я изменил его на 1000 (от его значения по умолчанию 100), но он не сделал никакой измеримой разницы. Отключить сбор мусора помогло - спасибо. Это было наибольшее ускорение до сих пор - экономия около 20% (171 минут на весь прогон, до 135 минут) - я не уверен , что на барах ошибки, но это должно быть статистически значимый увеличение. - Адам Неллис 9 февраля в 15:10

Мое предположение:

Я думаю, Python GC основан на счетчик ссылок. Время от времени он проверяет счетчик ссылок на каждый экземпляр; так как вы находитесь , проезжая эти огромные в памяти структуры, в вашем конкретном случае Частота по умолчанию GC (1000 циклов?) слишком часто уходит - огромный отходов. - Yours Truly Feb 10 at 2:06

Answer 2

Для этого потребуется немалая работа, но ... вы можете использовать Floyd-Warshall, работающий на графическом процессоре. Проделана большая работа над тем, чтобы Floyd-Warshall работал очень эффективно на GPU. Быстрый поиск в Google дает:

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

Несмотря на то, как это реализовано в Python, Флойд-Воршалла медленнее по порядку величины, хорошая версия графического процессора на мощном графическом процессоре может значительно превзойти ваш новый код Python.

Вот анекдот. У меня был короткий, простой, сложный вычислительный код, который делал что-то похожее на скопление hough. В Python, оптимизированном, как я мог его получить, потребовалось ~ 7 с быстрым i7. Затем я написал совершенно неоптимизированную версию графического процессора; на Nvidia GTX 480 было затрачено ~ 0,002. YMMV, но для чего-то значительно параллельного, GPU, вероятно, будет долгосрочным победителем, и поскольку он хорошо изученный алгоритм, вы должны иметь возможность использовать существующий высоконастроенный код ,

Для моста Python/GPU я бы рекомендовал PyCUDA или PyOpenCL.

Answer 3

Считаете ли вы, что Pyrex/Cython?

Он компилирует python в C, а затем в .pyd автоматически, поэтому он может ускорить работу до конца без большой работы.

Answer 4

Я не вижу ничего плохого в вашем коде относительно производительности (не пытаясь найти алгоритм), вы просто попадаете в большое количество итераций. Часть вашего кода будет выполнена 40 миллионов раз!

Обратите внимание, что 80% времени потрачено на 20% вашего кода - и это 13 строк, которые выполняются 24 миллиона раз. Кстати, с помощью этого кода вы предоставляете отличную иллюстрацию к Pareto principle (или «20% пьющих пива пьют 80% пива»).

Сначала первые: вы пробовали Psycho? Это компилятор JIT, который может значительно ускорить ваш код - учитывая большое количество итераций - скажем, в 4 раза-5x - и все, что вам нужно сделать (после загрузки и установки, конечно), - это вставить этот фрагмент в начало:

import psyco 
psyco.full() 

Вот почему я любил Psycho и использовал его в GCJ тоже, где время не имеет сущности - ничего кода, ничего получить не так и внезапное повышение от 2 линии добавлены.

Назад к nit-picking (который изменяется как замена == на is и т. Д., Из-за небольшого улучшения времени). Здесь они являются 13 линий «в вине»:

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) Кроме линий вы упоминаете, я замечаю, что # 388 имеет относительно высокое время, когда оно тривиально, все это делает его node_b_update = False. О, но подождите - каждый раз, когда он выполняется, False получает доступ в глобальном масштабе! Чтобы этого избежать, назначьте F, T = False, True в начале метода и замените последующие использования False и True с местными жителями F и T. Это должно уменьшить общее время, хотя и незначительно (3%?).

B) Я заметил, что условие в # 389 произошло «всего» 512120 раз (в зависимости от количества исполнений # 390) по сравнению с условием в № 391 с 16,251,407. Поскольку нет никакой зависимости, имеет смысл отменить порядок этих проверок - из-за раннего «сокращения», которое должно дать небольшой импульс (2%?). Я не уверен, избегая pass заявления вообще поможет, но если это не повредит читаемости:

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) Я просто заметил, что вы используете try-except в случае (# 365-367) нужно просто значение по умолчанию из словарь - попробуйте использовать вместо этого .get(key, defaultVal) или создайте свои словари с помощью collections.defaultdict(itertools.repeat(float('+inf'))). Использование try-except имеет его цену - см. # 365 отчетов в 3,5% случаев, это настройка кадров стека и еще много чего.

D) Избегайте индексированного доступа (будь то obj . поле или объект [ idx ]) если возможно.Например, я вижу, что вы используете self.node_distances[node_a] в нескольких местах (# 336, 339, 346, 366, 386), что означает, что для каждого использования индексирование используется дважды (один раз для . и один раз для []) - и это становится дорогим, когда выполняется десятки миллионы раз. Мне кажется, вы можете просто начать с метода node_a_distances = self.node_distances[node_a], а затем использовать его дальше.

Answer 5

Я бы разместил это как дополнение к моему вопросу, но Stack Overflow разрешает только 30000 символов, поэтому я отправляю это как ответ.

Update: Мои лучшие оптимизаций до сих пор

Я принял на Совет предложения людей, и теперь мой код работает около 21% быстрее, чем раньше, и это хорошо - спасибо всем!

Это лучшее, что мне удалось сделать до сих пор. Я заменил все тесты ==is для узлов, отключил сбор мусора и переписал большую часть заявления if на линии 388 в соответствии с предложениями @Nas Banov. Я добавил в хорошо известный try/except трюк, чтобы избежать тестов (строка 390 - удалить тест node_c in node_b_distances), который помог нагрузкам, поскольку вряд ли когда-либо выдает исключение. Я попытался переключить линии 391 и 392 вокруг и присвоить переменную node_b_distances[node_c], но этот путь был самым быстрым.

Однако я все еще не обнаружил утечку памяти (см. График в моем вопросе). Но я думаю, что это может быть в другой части моего кода (который я не размещал здесь). Если я смогу исправить утечку памяти, то эта программа будет работать достаточно быстро, чтобы я мог использовать :)

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