У меня есть рекурсивный алгоритм, который я использую для итерации по иерархической структуре данных, но, к сожалению, с некоторыми данными иерархическая структура настолько глубока, что Я получаю StackOverflowError. Я видел, как это происходит с глубиной около 150 узлов, в то время как данные потенциально могут расти намного дальше. Для контекста этот код будет работать в ограниченных средах, и изменение размера стека JVM не является опцией, а структура данных является заданной и представляет собой различные файловые системы с каталогами и файлами.Преобразование рекурсивного метода (где рекурсия выполняется внутри цикла) в итеративный метод
Чтобы обойти переполнение стека, я попытался преобразовать алгоритм в итеративный. Это не то, что мне приходилось делать раньше, поэтому я начал с некоторых примеров, показывающих, как это сделать с простой рекурсией, но я не уверен, как применить это к рекурсии внутри цикла. Я нашел способ сделать это, который, похоже, работает, но код довольно сумасшедший.
Вот упрощенная версия моего оригинального рекурсивного метода:
private CacheEntry sumUpAndCacheChildren(Node node) {
final CacheEntry entry = getCacheEntry(node);
if (entryIsValid(entry))
return entry;
Node[] children = node.listChildren();
long size = 0;
if (children != null) {
for (Node child : children) {
if (child.hasChildren()) {
size += sumUpAndCacheChildren(child).size;
} else {
size += child.size();
}
}
}
return putInCache(node, size);
}
Каждый узел лист имеет размер, в то время как размер для любого предка узла считается размер всех его потомков. Я хочу знать этот размер для каждого узла, поэтому размер агрегируется и кэшируется для каждого узла.
Вот итеративная версия:
private CacheEntry sumUpAndCacheChildren(Node initialNode) {
class StackFrame {
final Node node;
Node[] children;
// Local vars
long size;
// Tracking stack frame state
int stage;
int loopIndex;
StackFrame(Node node) {
this.node = node;
this.children = null;
this.size = 0;
this.stage = 0;
this.loopIndex = 0;
}
}
final Stack<StackFrame> stack = new Stack<StackFrame>();
stack.push(new StackFrame(initialNode));
CacheEntry retValue = getCacheEntry(initialNode);
outer:
while (!stack.isEmpty()) {
final StackFrame frame = stack.peek();
final Node node = frame.node;
switch(frame.stage) {
case 0: {
final CacheEntry entry = getCacheEntry(node);
if (entryIsValid(entry)) {
retValue = entry;
stack.pop();
continue;
}
frame.children = node.asItem().listChildren();
frame.stage = frame.children != null ? 1 : 3;
} break;
case 1: {
for (int i = frame.loopIndex; i < frame.children.length; ++i) {
frame.loopIndex = i;
final Node child = frame.children[i];
if (child.hasChildren()) {
stack.push(new StackFrame(child));
frame.stage = 2; // Accumulate results once all the child stacks have been calculated.
frame.loopIndex++; // Make sure we restart the for loop at the next iteration the next time around.
continue outer;
} else {
frame.size += child.size();
}
}
frame.stage = 3;
} break;
case 2: {
// Accumulate results
frame.size += retValue.size;
frame.stage = 1; // Continue the for loop
} break;
case 3: {
retValue = putInCache(node, frame.type);
stack.pop();
continue;
}
}
}
return retValue;
}
Это просто чувствует себя более безумным, чем это должно быть, и было бы болезненным, чтобы сделать это во всех местах в коде, где я рекурсию в дети и делают по-разному ops на них. Какие методы я могу использовать, чтобы упростить рекурсию, когда я агрегирую на каждом уровне и делаю это в цикле над детьми?
EDIT:
Я был в состоянии значительно упростить с помощью приведенных ниже ответов. Код теперь почти такой же сжатый, как исходная рекурсивная версия. Теперь мне просто нужно применять одни и те же принципы везде, где я рекурсирую по одной и той же структуре данных.
Порядок, в котором вы посещаете детей, не имеет значения, не так ли? – immibis
Вам необходимо проанализировать динамическую структуру данных. При реализации рекурсивного алгоритма переданные параметры создают структуру данных. В некоторых случаях эта структура тривиальна, в других - нет. Вам нужно выяснить, как поддерживать логически эквивалентную структуру данных в вашем итеративном алгоритме. –
Порядок не имеет значения, пока я могу получить сумму всех потомков на каждом узле. У меня есть некоторые другие варианты использования, хотя я делаю другие вещи для узлов, например. дублируя их или перемещая их на другое дерево. –