Сеть зависимых значений - как их пересчитать только один раз?

Question

Я надеюсь, что один из вас, ребята, сможет это выяснить.

У меня есть массив, содержащий множество объектов.Каждый объект в массиве содержит две вещи:

• Значение, которое может измениться.
• Список из нуля или более других объектов в моем массиве, который, если их значения меняются, тогда этот объект должен пересчитать его значение.Это может происходить многократно от объекта к объекту, но нет циклических зависимостей.

Я считаю, что это называется сетью (как дерево, но с несколькими родителями). В частности, это направленный ациклический граф.

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

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

Какой лучший способ пересчитать каждый объект только один раз, после того как все его родители пересчитали?

Спасибо за вашу помощь.

Answer 1

Звучит так, как будто вы хотите Топологическая сортировка направленного ациклического графа . См. Например http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/DAG/

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

Answer 2

Создание ациклического орграфа с вершинами, заданными узлами в вашем массиве, и ребром i --> j всякий раз, когда изменение в i требует повторного вызова j (т.е. i находится в списке для объекта j ). График является ациклическим, если ваш процесс конечен.

Теперь, когда i изменяется, сначала выполните поиск в ширину, чтобы пересчитать зависимые узлы. При первом проходе соберите все узлы j, чтобы i --> j. Пересчитайте те j. На втором проходе возьмите каждый j , который изменил , и получите его зависимых j --> k. Затем пересчитайте эти k сразу. Продолжайте, беря все иждивенцы k s , которые изменились , и так далее, пока не останутся только листья.

Это требует, чтобы вы вели список соседей, который противоположен имеющейся у вас информации. Поэтому вам нужно сделать один проход, чтобы получить направленные ребра (заполните массив так, чтобы запись i содержала массив всех j, для которых i --> j).

Answer 3

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

Псевдокод:

Create a set S 
Add initially updated element to S
while S is not empty
    remove an element X from S whose value does not depend on any other elements in E do not exist in S
    recalculate X's value and add any elements that depend on X's value to S