-There's a <TL;DR> section down below-
Здравствуйте,
Допустим, мне нужен алгоритм для обработки каждого узла в дереве, учитывая, что:
- Дерево ОГРОМНОЕ
- Обработка каждого узла требует ВРЕМЕНИ.
Это основная c** рекурсивная функция обхода:
function process_branch(node)
process_node(node)
for each c in node.children
process_branch(c)
end for
end function
Теперь это итеративная версия, использующая мою собственный стек:
function process_branch(node)
stack.push(node)
while not stack.empty
n=stack.pop()
process_node(n)
for each c in n.children
stack.push(c)
end for
end while
end function
** Все алгоритмы, которые я разместил здесь, являются чрезвычайно упрощенными версиями реальных.
Пока все хорошо.
Подробнее рассмотрим:
- Я использую итеративное решение, чтобы избежать переполнения стека вызовов. Фактически, использование моего собственного стека позволяет мне перехватывать исключения, связанные с отсутствием памяти, и сразу же останавливать функцию.
- Как я уже упоминал, размер дерева огромен, и нет способа вычислить требуемую память в заранее.
- Результаты обработки каждого узла, их статусы и т. д. c. хранятся в базе данных . Таким образом, если достигнут предел памяти или функция остановлена другими условиями (включая пользовательское), ничего не теряется.
Но тогда, Мне нужен способ вызова функции снова, возобновляя обработку и игнорируя уже полные ветки .
-<TL;DR> section starts here-
Эта рекурсивная версия творит чудеса:
function process_branch(node)
if not node.completed
process_node(node)
for each c in node.children
process_branch(c)
end for
node.completed=true
end if
end function
Обратите внимание, как узел root ветки отмечен только как завершенные, когда все их дети также завершены. Итак, каждый раз, когда функция перезапускается, сохраняется много работы.
Моя проблема: Мне не удалось создать итеративную версию этой новой функции.
Это итеративная версия, которая у меня есть прямо сейчас:
function process_branch(node)
stack.push(node)
while not stack.empty
n=stack.pop()
if not n.completed
process_node(n)
for each c in n.children
stack.push(c)
end for
n.completed=true
end if
end while
end function
Обратите внимание, как данный узел помечается как завершенный даже до того, как его дочерние ветви будут фактически обработаны .
При рекурсии оператор n.completed = true откладывался до каждого process_branch (c) для своих дочерних элементов (и дочерних элементов дочерних элементов, et c .) был завершен.
<TL;DR> section ends here
Итак, если функция остановлена в середине этого, будет некоторая целая ветвь, отмеченная как завершенная (что неверно), и она будет проигнорирована в следующем перезапуск функции.
Как мне реализовать отложенное n.completed = true в итеративной версии?
Я не вижу этого. Надеюсь, это просто блок ума.
Спасибо за вашу помощь!
EDIT:
Спасибо за предложения по игре со стеком, Я нашел простое решение, которое в основном требует двух вещей:
- Проталкивание родительского узла (снова) перед его дочерними элементами, поэтому после обработки каждого дочернего узла основной l oop может возвращаться к нему и установите его как завершенное.
- Введение нового статуса / свойства для каждого узла («обработано»), чтобы различать обработанные узлы и пропускать уже завершенную работу. Обратите внимание, что это необходимо, потому что обработка каждого узла происходит, как только он достигает . Или, другими словами, узел обрабатывается задолго до того, как его ветвление завершено.
function process_branch(node)
stack.push(node)
while not stack.empty
n=stack.pop()
if not n.completed
if not n.processed
process_node(n)
end if
t=0
for each c in n.children
if not c.completed
t=t+1
end if
end for
if t=0
n.completed=true
else
stack.push(n)
end if
for each c in n.children
if not c.completed
stack.push(c)
end if
end for
end if
end while
end function
Надеюсь, это кому-то поможет в будущем.