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

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

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

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

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

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

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

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

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

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

Фактическая функция, с которой у меня возникают проблемы: propagate_distances_node() выполняет один шаг протокол маршрутизации между векторами. Учитывая node, node_a, функция гарантирует, что node_a соседи правильно расположены в матрице расстояний (изменения топологии). Затем функция отправляет таблицу t28 > маршрутизации ко всем node_a ближайшим соседям в сети. Он объединяет таблицу маршрутизации node_a с каждой соседней собственной таблицей маршрутизации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответы

Ответ 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.

ОБНОВЛЕНИЕ

Я сделал этот небольшой эксперимент (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).
не было большой разницы между is и '==', по крайней мере для простых объектов

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

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

Вы используете 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 циклы?) слишком часто - огромный отходы. - С уважением, 10 февраля в 2:06

Ответ 2

Вы считали Pyrex/Cython?

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

Ответ 3

Для этого потребуется немалая работа, но... вы можете использовать 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

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

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

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

Ответ 4

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

Обратите внимание, что 80% времени потрачено на 20% вашего кода - и это 13 строк, которые выполняются в 24 миллиона раз. Кстати, с помощью этого кода вы прекрасно представляете принцип Парето (или "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 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 на locals 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 . или obj [ idx ]), когда это возможно. Например, я вижу, что вы используете self.node_distances[node_a] в нескольких местах (# 336, 339, 346, 366, 386), что означает, что для каждого использования индексирование используется дважды (один раз для . и один раз для [])), и это дорожает, когда исполняется десятки миллионов раз. Мне кажется, вы можете просто начать с начала метода node_a_distances = self.node_distances[node_a], а затем использовать его далее.

Ответ 5

Я бы разместил это как обновление для моего вопроса, но Qaru разрешает только 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 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 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 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 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 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 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 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 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)