понедельник, 12 апреля 2010 г.

LINQ-ом по деревьям (часть 2)

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

Walk

С прошлого поста заменил Enumerable.Repeat(root, 1) на new [] {root}.
public static IEnumerable<T> Walk<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new []{root}.Concat(q);
}

Walk2

Слегка оптимизированная версия Walk, где методы SelectMany и Concat развернуты в конечный автомат yield return:
public static IEnumerable<T> Walk2<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    yield return root;
    foreach (var child in next(root))
    {
        foreach (var node in Walk2(child, next))
        {
            yield return node;
        }
    }
}
Эта версия Walk метода покажет нам ценность такого переписывания. Я не буду пропагандировать ни за ни против, просто предоставлю данные, а решать пусть будет каждый сам за себя, пользоваться ли высокоуровневыми методами, либо эквивалентными циклами.

WalkS

WalkS – обход с помощью структуры Stack<T>. Это самый простой способ преобразования callstack-а в структуру данных.
public static IEnumerable<T> WalkS<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current).Reverse())
        {
            stack.Push(x);
        }
    }
}
Здесь использован метод Enumerable.Reverse чисто для сохранения порядка обхода в соответствии с оригинальным методом Walk. Но гоняться в бенчмарке будет немного другой метод:

WalkS2

У этой модификации используется 2 стека (Stack<T>). Второй заменяет Enumerable.Reverse.
public static IEnumerable<T> WalkS2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    var stack2 = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current))
        {
            stack2.Push(x);
        }
        foreach (var x in stack2)
        {
            stack.Push(x);
        }
        stack2.Clear();
    }
}

WalkL

В очередной модификации вместо Stack<T> используется односвязный список.
class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}
public static IEnumerable<T> WalkL<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var current = list;
        list = list.Next;
        yield return current.Value;

        foreach (var x in next(current.Value).Reverse())
        {
            list = new ListNode<T>(x, list);
        }
    }
}
Но воевать будет не она, а та что использует 2 односвязных списка:

WalkL2

Последняя модификация, учавствующая в бенчмарке использует один список для замены callstack-а, другой вместо Enumerable.Reverse().
public static IEnumerable<T> WalkL2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        foreach (var v in next(currentNode.Value))
        {
            tmpList = new ListNode<T>(v, tmpList);
        }

        if(tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Depth

В бенчмарке учавствует еще один метод, который тоже обходит дерево, но при этом не пытается выпрямить его узлы в последовательность. Подсчет глубины конкретного двоичного дерева в чисто рекурсивной форме. Этот метод будет эталоном скорости.
Вслед за методом GetDepth привел класс узла дерева, на котором проходил бенчмарк.
public static int GetDepth<T>(this Node<T> node)
{
    return (node == null)
        ? 0
        : 1 + Math.Max(
            node.Left.GetDepth(),
            node.Right.GetDepth());
}

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

Забег №1

Случайным образом перемешанный массив индексов [0..N] подается на вход алгоритму, строящему двоичное дерево (без балансировки). Полученное дерево скармливается вышеуказанным методам Walk* и у полученного IEnumerable<int> извлекается последний элемент Enumerable.Last ().
Результаты первого забега (по оси x кол-во элементов, по y – время обхода в секундах):

Следующим образом выглядит таблица времен обхода дерева из 10М элементов:
Метод обхода
Время
Walk
00:00:24.7759974
Walk2 00:00:10.8108170
WalkS2 00:00:03.5185059
WalkL2 00:00:02.7030328
Depth 00:00:01.0753161
Что-то здесь не так. Судя по графику, нерекурсивные методы значительно быстрее, но я не увидел зависимости графиков рекурсивных методов от глубины дерева… И деревья-то подсовывались не слишком глубокие. Глубина дерева из случайно перемешанного набора из 20М индексов не превышала 60. При таком подходе, увеличивая вдвое число элементов, мы будем получать увеличение глубины дерева лишь на единицу. Геометрическая, блин, прогрессия! Страшно подумать, сколько нужно элементов, для того чтобы достичь глубины 1000 :(
Но кое-какие выводы можно сделать и из этого забега:
  • Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
  • Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
  • Односвязные списки немного шустрее чем Stack<T>.

Забег №2

То же самое двоичное дерево, но исходные данные теперь не перемешаны, потому получается вырожденное в список дерево, чья глубина будет равна числу элементов. Элементов будет мало, но теперь дерево будет сосредоточено в глубину.

Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (полагаю что JIT распознал хвостовую рекурсию и преобразовал рекурсию в цикл это не так, спасибо Пельмешко за внимательность. GetDepth-у для исключения нужно глубину 65000).


Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном но преобразованном в цикл методе GetDepth. Т.е. их зависимость от глубины на этом графике не видна. Время, которое показывали три последних метода на обходе 10000 элементов не превышало 0.001 секунды.

Итого:

Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 10К. На глубинах дерева до 1000 рекурсивными перечислителями вполне можно пользоваться и их производительность хоть и уступает нерекурсивным методам,  но может быть вполне приемлема для множества задач.

P.S.

На RSDN Sinix-ом был приведен другой метод выпрямления рекурсивных комбинаций перечислителей. Нетрудно увидеть схожесть его метода с представленными мной. Отличия в сигнатуре (принимает коллекцию узлов), в порядке обхода (нет Reverse), да и в стек он помещает не узлы, а перечислители узлов. Не знаю, в чем фокус, но его метод работает примерно в 2 раза медленнее WalkS2, представленного мной (с Reverse-ом с помощью дополнительного стека). Ну и собственно название, UngroupRecurseEnumerator сбивает с толку. Это тот же самый обход дерева.

P.P.S.

В этой статье упоминается Range через yield foreach:
static IEnumerable<int> FromTo(int b, int e)
{
    if (b > e)
        yield break;
    yield return b;
    yield foreach FromTo(b + 1, e);
}
А вот и наш ответ Чемберлену
static IEnumerable<int> FromTo(int b, int e)
{
    return b.WalkL2(i =>
         (i < e)
            ? new int[] { i+1 } 
            : new int[] {});
}
Не столь красивый, но не требующий изменения языка.
А yield foreach все-таки сила!

Upd.

Я таки написал версию GetDepth с хвостовой рекурсией:
public static int GetDepthC<T>(this Node<T> node)
{
    return GetDepthCps(node, d => d);
}

static int GetDepthCps<T>(Node<T> node, Func<int, int> cont)
{
    return (node == null)
       ? cont(1)
       : GetDepthCps(node.Left, leftDepth =>
            GetDepthCps(node.Right, rightDepth =>
                cont(Math.Max(leftDepth, rightDepth))));
}
Естественно я не ожидал что C# ее выпрямит в цикл. А вот F# выпрямляет!
Если будут пожелания, можно в другой раз написать что-то вроде "CPS для чайников". Толку, правда, будет немного в рамках C#. Но разжевать предмет можно попробовать.

7 комментариев:

  1. Спасибо за продолжение! :)

    Вот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет, так как в ветке if не сразу вызов самого себя, а вычисление "1 + Math.Max(...)". Насколько мне известно, JIT не умеет делать таких сложных преобразований, как развёртывание хвостовой рекурсии в цикл. Возможно дело в том, что GetDepth() делает очень мало выделения памяти на стеке (если вообще делает) и поэтому является более стойким к переполнению стека. Думаю GetDepth() всё равно зависит от глубины и это будет заметно на больших размерах деревьев....

    ОтветитьУдалить
  2. Пельмешко>Вот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет
    Ты абсолютно прав в том что это не хвостовая рекурсия. Что-то я дал маху. Я с этим делом знаком, но вот тут что-то сглупил.

    Однако, JIT в некоторых случаях выпрямляет хвостовую рекурсию в цикл (см конец статьи http://lookingsharp.wordpress.com/2010/03/08/tail-recursion-in-csharp-and-fsharp/).

    А в моем случае - да, глубина 65000 для GetDepth критична. Поправлю статью.

    Спасибо за внимательность!

    ОтветитьУдалить
  3. Пельмешко>Вот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет

    Дописал вариант с хвостовой рекурсией (см. конец публикации)

    ОтветитьУдалить
  4. Возможно стоит в первой реализации Walk2 внутри foreach исользовать Walk2 а не Walk ?

    ОтветитьУдалить
  5. >Анонимный комментирует...

    Возможно стоит в первой реализации Walk2 внутри foreach исользовать Walk2 а не Walk ?

    Благодарю за внимательность. Исправленный Walk2 заработал в 2 раза быстрее, чем исходный. Графики и таблицу времен результатов для 10M забега обновил.

    ОтветитьУдалить
  6. Компилятор C# не распознает хвостовые рекурсии.

    ОтветитьУдалить
  7. Верно, компилятор C# даже не пытается их распознавать. Но он и не является конечной инстанцией в этой оптимизации.
    JIT - умеет (см. http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx)

    ОтветитьУдалить