Направленный ациклический граф CouchDB (DAG) - PullRequest
Новая
       5

Направленный ациклический граф CouchDB (DAG)

3 голосов
/ 18 сентября 2010

Если моя структура выглядит так: 

[{Name: 'A', Depends: []},
{Name: 'B', Depends: ['A']},
{Name: 'C', Depends: ['A']},
{Name: 'D', Depends: ['C']},
{Name: 'E', Depends: ['D','B']}]

Как бы я написал карту и сократил функции так, чтобы мой вывод был: 

[{Key: 'A', Value: []},
{Key: 'B', Value: ['A']},
{Key: 'C', Value: ['A']},
{Key: 'D', Value: ['A','C']}
{Key: 'E', Value: ['D','B','C','A']}]

Я понял, что функция map должна выкидывать свои зависимости, но я не знаю, как их будет удерживать Reduce, чтобы их можно было применять ниже по дереву, не выбрасывая производительность в окно и не ожидая всех сопоставления для применения. Я также не могу использовать пути, потому что не всегда существует уникальный путь (например, D A-> C-> D или A-> D).

Ответы [ 2 ]

0 голосов
/ 29 сентября 2010

Вам нужна вторая или вспомогательная база данных couchdb, назовем ее «complete_dependencies». Его документами будут рассчитанные полные зависимости каждого узла. Документы будут иметь вид

{Имя: 'D', CompleteDepends: ['C', 'A']}

Также этот БД будет иметь представление «подразумевает», показывающее для каждого элемента все элементы, которые зависят от него. Для предыдущего элемента он выдаст:

[{Имя: 'C', подразумевает: 'D'}, {Имя: 'A', подразумевает: 'D'}]

Вы будете использовать API уведомлений об изменениях для актуализации этой базы данных. Он обработает каждый документ, который был изменен в исходной БД, и рассчитает его полные зависимости. Обратите внимание, что эта обработка не является представлением. Является ли программа сделанной на ваш язык, слушая изменения API и обрабатывая каждый документ. Для каждого документа будет сделано следующее:

1) вычислить его полные зависимости, используя нашу базу данных complete_dependencies.

2) посмотрите в представлении «подразумевает», какие документы зависят от измененного документа, и пересчитайте их. Вот одна вещь, чтобы позаботиться. Чтобы использовать complete_dependencies, они должны быть правильно рассчитаны, поэтому перед использованием записи complete_dependencies документа вы должны быть уверены, что документ отсутствует в списке «подразумеваемых» или что он рассчитан.

Важным моментом является то, что ни одна из этих функций не является рекурсивной.

Из этого следует:

Первый документ: {Имя: 'A', Зависит от: []}. Поскольку нет зависимостей (1), он ничего не будет делать, так как представление подразумевает, что оно пустое (2) также ничего не сделает.

Второй {Имя: 'B', Зависит: ['A']}. Он будет смотреть на 'A' в db complete_dependencies, чтобы увидеть, зависит ли это от чего-то. Поскольку нет никаких зависимостей от 'A', он будет писать только {Имя: 'B', CompleteDepends: ['A']}. (2) не найдет элемент, который зависит от 'B', поэтому он ничего не будет делать.

То же самое для {Имя: 'C', Зависит: ['A']} -> {Имя: 'C', CompleteDepends: ['A']}.

Когда он читает следующий документ {Имя: 'D', Зависит: ['C']}, он обнаруживает, что 'C' зависит от 'A', поэтому он будет писать

{Имя: 'D', CompleteDepends: ['C', 'A']}

Важно: он не должен проверять рекурсивные зависимости 'A', поскольку он ищет в C "CompleteDependencies", и все зависимости A должны находиться в полных зависимостях C.

Когда он обрабатывает следующий документ {Имя: 'E', Зависит: ['D', 'B']}, он будет искать зависимости 'D' и 'B' Complete и обнаружит, что D complete зависит от C и A и B только в A. {Имя: 'E', CompleteDepends: ['D', 'B', 'C', 'A']}.

Теперь давайте предположим, что он получает новую версию документа 'A': {Имя: 'A', Зависит: ['Z']}. Теперь это должно

1) вычислить полные зависимости 'A' -> {Имя: 'A', CompleteDepends: ['Z']}

2) посмотреть, какие элементы зависят от «A», и пересчитать его полные документы зависимостей. Он пересчитает полные зависимости B, C, D, E.

Давайте рассмотрим другой случай. Предположим, мы получили новую версию документа C: {Имя: 'C', Зависит от: ['Z']}.

(1) будет сгенерирован документ {Имя: 'C', CompleteDepends: ['Z']}.

Поиск элементов, зависящих от C, найдет D и E. Теперь, если он сначала вычислит E, он обнаружит, что он зависит от D, и, поскольку D имеет значение для C, он должен сначала пересчитать D. Это единственное эта функция (2) должна заботиться.

Я думаю, что для этого функция «Пересчитать» должна иметь список «грязных» элементов, которые включают в себя весь список «подразумеваемых» и исключаются при вычислении одного из них.

0 голосов
/ 29 сентября 2010

Если на самом деле речь идет о javascript, то я полагаю, вам не из чего выбирать.

Возможно, вы захотите написать собственную реализацию этого: http://www.electricmonk.nl/log/2008/08/07/dependency-resolving-algorithm/

Для хранения наборов (массив только с уникальными значениями) я рекомендую использовать ассоциативный массив и использовать его ключи.

Также может быть полезна функция Array.map ().

...