Блог

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод:

 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