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

Question

Вопрос:

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

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

Мой код:

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

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

Я рассматривал возможность использования NumPy (так как он использует разреженные матрицы), но я не думаю, что это уместно, потому что: (1) я не индексирую свою матрицу, используя целые числа (I 'используя экземпляры объектов);и (2) я не храню простые типы данных в матрице (я храню кортежи с плавающей точкой и экземпляром объекта).Но я хочу, чтобы меня убедили в 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():
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)

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

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

Существует объект, представляющий матрицу расстояний: self.node_distances.Это словарь, отображающий узлы в таблицы маршрутизации.Узел - это объект, который я определил.Таблица маршрутизации - это словарь, сопоставляющий узлы с кортежами (distance, next_node).Расстояние - это расстояние на графике от узла_а до узла_б, а следующий_узел - это сосед узла_a, к которому вы должны перейти первым, на пути между узлами_а и нодами_b.Следующий_узел 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() выполняет один шаг из протокола маршрутизации с вектором расстояния . Для данного узла node_a функция гарантирует, что соседи node_a правильно находятся в матрице расстояний (изменения топологии). Затем функция отправляет таблицу маршрутизации node_a всем ближайшим соседям node_a в сети. Он объединяет таблицу маршрутизации node_a с собственной таблицей маршрутизации каждого соседа.

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

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

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

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

Обновление:

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

Обновление: Существующие библиотеки

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

*1000* NetworkX было предложено @Thomas K.Он имеет множество алгоритмов для вычисления кратчайших путей.У него есть алгоритм для вычисления длины кратчайшего пути для всех пар с отсечкой (что я и хочу), но он работает только на невзвешенных графах (мои взвешены).К сожалению, его алгоритмы для взвешенных графов не позволяют использовать отсечение (что может сделать их медленными для моих графов).И ни один из его алгоритмов, кажется, не поддерживает использование предварительно рассчитанных путей в очень похожей сети (то есть маршрутизации).

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

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

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

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

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

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

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

И расстояние между шипами на графике ввода-вывода увеличивается со временем.Это плохо - моя программа выводит на экран каждые 100 000 итераций, так что это означает, что каждая итерация занимает больше времени с течением времени ... Я подтвердил это, выполнив длинный прогон моей программы и измерив время междуоператоры печати (время между каждыми 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

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

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

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

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

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

vmstat 10 100

Удачи!

ОБНОВЛЕНИЕ (из комментариев ОП)

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

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

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

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

Answer 2

Рассматривали ли вы Pyrex / Cython ?

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

Answer 3

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

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

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

import psyco
psyco.full()

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

Вернемся к придиркам (которые меняются как замена == на 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-исключения имеет свою цену - см. Отчеты № 365 в 3,5% случаев, это настройка фреймов стека и еще много чего.

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

Answer 4

Это потребует значительного объема работы, но ... вы можете рассмотреть возможность использования Floyd-Warshall на GPU. Была проделана большая работа по созданию очень эффективной работы 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, Floyd-Warshall был на порядок медленнее, хорошая версия графического процессора на мощном графическом процессоре может все же значительно превзойти ваш новый код Python.

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

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

Answer 5

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

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

Я учел предложения людей, и теперь мой код работает примерно на 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)):
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)