Итак, в бенчмарке присутствуют следующие методы:
Walk
С прошлого поста заменил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 |
Но кое-какие выводы можно сделать и из этого забега:
- Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
- Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
- Односвязные списки немного шустрее чем Stack<T>.
Забег №2
То же самое двоичное дерево, но исходные данные теперь не перемешаны, потому получается вырожденное в список дерево, чья глубина будет равна числу элементов. Элементов будет мало, но теперь дерево будет сосредоточено в глубину.Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (
Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном
Итого:
Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 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#. Но разжевать предмет можно попробовать.
Спасибо за продолжение! :)
ОтветитьУдалитьВот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет, так как в ветке if не сразу вызов самого себя, а вычисление "1 + Math.Max(...)". Насколько мне известно, JIT не умеет делать таких сложных преобразований, как развёртывание хвостовой рекурсии в цикл. Возможно дело в том, что GetDepth() делает очень мало выделения памяти на стеке (если вообще делает) и поэтому является более стойким к переполнению стека. Думаю GetDepth() всё равно зависит от глубины и это будет заметно на больших размерах деревьев....
Пельмешко>Вот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет
ОтветитьУдалитьТы абсолютно прав в том что это не хвостовая рекурсия. Что-то я дал маху. Я с этим делом знаком, но вот тут что-то сглупил.
Однако, JIT в некоторых случаях выпрямляет хвостовую рекурсию в цикл (см конец статьи http://lookingsharp.wordpress.com/2010/03/08/tail-recursion-in-csharp-and-fsharp/).
А в моем случае - да, глубина 65000 для GetDepth критична. Поправлю статью.
Спасибо за внимательность!
Пельмешко>Вот только насчёт GetDepth(): никакой хвостовой рекурсии в нём нет
ОтветитьУдалитьДописал вариант с хвостовой рекурсией (см. конец публикации)
Возможно стоит в первой реализации Walk2 внутри foreach исользовать Walk2 а не Walk ?
ОтветитьУдалить>Анонимный комментирует...
ОтветитьУдалитьВозможно стоит в первой реализации Walk2 внутри foreach исользовать Walk2 а не Walk ?
Благодарю за внимательность. Исправленный Walk2 заработал в 2 раза быстрее, чем исходный. Графики и таблицу времен результатов для 10M забега обновил.
Компилятор C# не распознает хвостовые рекурсии.
ОтветитьУдалитьВерно, компилятор C# даже не пытается их распознавать. Но он и не является конечной инстанцией в этой оптимизации.
ОтветитьУдалитьJIT - умеет (см. http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx)