Как сложить n-арное дерево в C #

Я хотел бы сделать свертку над n-арными структурами данных Tree. (fold - это также Aggregate в Linq). Мне удалось найти рабочее решение:

public static R Aggregate<T, R>(T node,
          Func<T, IEnumerable<T>> getChildren,
       Func<T, IEnumerable<R>, R> aggregator)
{
    var childResults = getChildren(node)
                      .Select(c => Aggregate(c, getChildren, aggregator));

    return aggregator(node, childResults);
}

getChildren - функция, определяющая, как получить потомков данного узла. Он должен возвращать пустой IEnumerable для конечных узлов.
aggregator определяет, как обрабатывать узел, используя текущий узел и результаты его дочерних узлов.

Решение вроде работает, но есть некоторые проблемы:

  • Алгоритм является рекурсивным, он взорвет стек для глубоких деревьев.
    Как я могу переписать функцию, чтобы предотвратить переполнение стека?

  • Алгоритм ленивый, но не более чем.
    например. если aggregator использует только результат Enumerable.First дочерних узлов, будет пройдена только самая левая ветвь дерева. Однако с Enumerable.Last обход выполняется по всему дереву, даже если для вычислений требуется только самая правая ветвь.
    Как я могу сделать алгоритм действительно ленивым?

Решения F # приветствуются, но предпочтительнее C #.


c# f# tree fold catamorphism
person 3dGrabber    schedule 23.10.2013    source источник
comment
Когда вы изначально строили дерево, у вас не было глубокого стека? Итак, почему этот алгоритм взорвет стек, если у вас уже был стек n-deep при построении дерева?   -  person philologon    schedule 23.10.2013
comment
@philologon: не обязательно, чтобы все дерево было в памяти сразу. Примером может служить сетевой сканер.   -  person 3dGrabber    schedule 24.10.2013
comment
Используйте продолжения или батут.   -  person Mauricio Scheffer    schedule 24.10.2013
comment
@MauricioScheffer: Как?   -  person 3dGrabber    schedule 24.10.2013
comment
@ 3dGrabber см. Статьи Брайана Макнамара в en.wikipedia.org/wiki/Catamorphism#External_links   -  person Mauricio Scheffer    schedule 27.10.2013
comment
@MauricioScheffer: Я знаю эти статьи. К сожалению, они касаются бинарных деревьев (не n-арных) в F # и используют хвостовую рекурсию, которая не работает в C #.   -  person 3dGrabber    schedule 28.10.2013

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете перемещаться по дереву, используя явный стек, а не рекурсию, чтобы избежать использования пространства стека:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

Если вы хотите затем перемещаться "назад", вы можете просто настроить дочерний селектор при его вызове, вместо вызова Last вместо First:

Traverse(root, node => nodes.Reverse());
person Servy    schedule 23.10.2013
comment
Речь идет о сворачивании (или агрегировании, сворачивании), а не прохождении. - person 3dGrabber; 24.10.2013
comment
@ 3dGrabber Если у вас есть упорядоченная последовательность элементов, вы можете просто использовать LINQ Aggregate для этой последовательности. - person Servy; 24.10.2013
comment
Неа. Это преобразует дерево в список и сворачивает список. Результат (в общем) не тот. См. Требование: агрегатор определяет, как обрабатывать узел , используя текущий узел и результаты его дочерних узлов. - person 3dGrabber; 24.10.2013

arrow_upward
0
arrow_downward

  • У вас есть трата памяти при обходе деревьев, если вы хотите сохранить стек, вместо переключения глубины сначала на ширину или какой-либо метод обхода дерева, соответствующий вашим точным требованиям.

  • Что касается "правильной" ленивости, отключите агрегатор от обхода. Просто сначала создайте ленивый обход (в любом желаемом порядке) и передайте его своему агрегатору.

Кроме того, не очень уверен в выборе интерфейса по отношению к вашей лени. Enumerable.First vs Enumerable.Last даст разные результаты для одного и того же дерева в зависимости от изменения поставщика (getChildren), так зачем думать о лени? Итак, я думаю, что схема упорядочивания / обхода (даже сначала в глубину, а в ширину) должна быть присуща вашему агрегатору или фиксироваться для типа дерева? не внешний параметр?

person Vivek    schedule 23.10.2013