Оптимизация кода доступа к словарю Python
Вопрос:
Я до смерти профилировал свою программу Python, и есть одна функция, которая все тормозит. Он сильно использует словари Python, поэтому я, возможно, использовал их не лучшим образом. Если я не смогу заставить его работать быстрее, мне придется переписать его на C ++, так есть ли кто-нибудь, кто может помочь мне оптимизировать его на Python?
Я надеюсь, что дал правильное объяснение, и что вы можете понять мой код! Заранее благодарим за любую помощь.
Мой код:
Это вызывающая нарушение функция, профилированная с использованием line_profiler и kernprof . Я использую Python 2.7
. Меня особенно озадачивают такие вещи, как строки 363, 389 и 405, где оператор if со сравнением двух переменных, кажется, занимает чрезмерно много времени.
Я рассматривал возможность использования NumPy (поскольку он работает с разреженными матрицами), но я не думаю, что это ' уместно, потому что: (1) я не индексирую свою матрицу с помощью целых чисел (я использую экземпляры объектов); и (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 - это расстояние графа от node_a до node_b, а next_node - это сосед node_a, к которому вы должны перейти первым, на пути между node_a и node_b. Значение next_node, равное 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.node_distances , но содержит информацию о прямых связях (ребрах) в сети. self.neighbours постоянно модифицируется извне по отношению к этой функции посредством химической реакции. Отсюда и происходят изменения топологии сети.
Фактическая функция, с которой у меня возникли проблемы: progate_distances_node () выполняет один шаг протокола маршрутизации вектора расстояния . Для данного узла, node_a , функция проверяет, что соседи node_a правильно находятся в матрице расстояний (топология изменяется). Затем функция отправляет таблицу маршрутизации node_a всем ближайшим соседям node_a в сети. Он объединяет таблицу маршрутизации node_a с собственной таблицей маршрутизации каждого соседа.
В остальной части моей программы функция progate_distances_node () вызывается повторно, пока матрица расстояний не сойдется. Поддерживается набор self.nodes_changed узлов, которые изменили свою таблицу маршрутизации с момента последнего обновления. На каждой итерации моего алгоритма выбирается случайное подмножество этих узлов, и на них вызывается roprate_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), , но это замедлило работу! (Я этого не ожидал!)
Я попытался заменить каждый экземпляр node_x == node_y на node_x is node_y (согласно комментарию @Sven Marnach), , но это замедлило работу! (Я этого не ожидал!)
Я попытался заменить каждый экземпляр node_x == node_y на node_x is node_y (согласно комментарию @Sven Marnach), , но это замедлило работу! (Я этого не ожидал!)
Для запуска моего исходного профиля потребовалось 807,234 с, но с этой модификацией оно увеличилось до 895,895 с. Извините, я неправильно выполнял профилирование! Я использовал line_by_line, который (в моем коде) имел слишком большую дисперсию (эта разница в ~ 90 секунд была связана с шумом). При правильном профилировании значительно быстрее, чем == . Используя CProfile , мой код с == занял 34,394 секунды, но с - , потребовалось 33,535 секунды (что, я могу подтвердить, не вызывает шума).
Обновление: Существующие библиотеки
Я не уверен, будет ли существующая библиотека, которая может делать то, что я хочу, поскольку мои требования необычны: Мне нужно вычислить длину кратчайшего пути между всеми парами узлов в взвешенном неориентированном графе. Меня интересуют только длины пути ниже порогового значения. После вычисления длины пути я вношу небольшое изменение в топологию сети (добавляя или удаляя ребро), а затем хочу пересчитать длину пути. Мои графики огромны по сравнению с пороговым значением (от данного узла большая часть графика находится дальше, чем пороговое значение), поэтому изменения топологии не влияют на большинство длин кратчайшего пути. Вот почему я использую алгоритм маршрутизации: потому что он распространяет информацию об изменении топологии по структуре графа, поэтому я могу остановить ее распространение, когда она выйдет за пределы порогового значения. т.е. мне не нужно каждый раз заново вычислять все пути. Я могу использовать предыдущую информацию о пути (до изменения топологии), чтобы ускорить расчет. Вот почему я думаю, что мой алгоритм будет быстрее, чем любые библиотечные реализации алгоритмов кратчайшего пути. Я никогда не видел, чтобы алгоритмы маршрутизации использовались помимо маршрутизации пакетов по физическим сетям (но если кто-то и использовал, то мне было бы интересно).
NetworkX был предложен @Thomas K. Он имеет множество алгоритмов для вычисления кратчайших путей. У него есть алгоритм для вычисления длин кратчайших путей для всех пар с отсечкой (это то, что я хочу), но он работает только на невзвешенных графах (мои - взвешенные). К сожалению, его алгоритмы для взвешенных графов не позволяют использовать обрезание (что может замедлить их работу для моих графиков). И ни один из его алгоритмов, похоже, не поддерживает использование предварительно рассчитанных путей в очень похожей сети (т. Е. Маршрутизации).
igraph - еще одна библиотека графов, о которой я знаю, но глядя на ее документация , я ничего не могу найти о кратчайших путях. Но я, возможно, пропустил его - его документация не кажется очень исчерпывающей.
NumPy может быть возможным благодаря комментарию @ 9000. Я могу сохранить свою разреженную матрицу в массиве NumPy, если я назначу уникальное целое число каждому экземпляру моих узлов. Затем я могу проиндексировать массив NumPy целыми числами вместо экземпляров узлов. Мне также понадобятся два массива NumPy: один для расстояний и один для "
И расстояние между пиками на графике ввода-вывода со временем увеличивается. Это плохо - моя программа выводит на экран каждые 100000 итераций, так что это означает, что выполнение каждой итерации с течением времени занимает больше времени ... Я подтвердил это, выполнив длительный прогон моей программы и измерив время между операторы печати (время между каждыми 10 000 итерациями программы). Оно должно быть постоянным, но, как вы можете видеть на графике, оно линейно увеличивается ... так что что-то там есть. (Шум на этом графике вызван тем, что моя программа использует множество случайных чисел, поэтому время для каждой итерации варьируется.)
После того, как моя программа работала в течение длительного времени, использование памяти выглядит следующим образом (так что она определенно не работает вне ОЗУ):
