Эффективный обход графов с помощью LINQ - устранение рекурсии
Сегодня я собирался реализовать метод для прохождения произвольно глубокого графа и объединения его в одно перечислимое. Вместо этого я сначала немного искал и нашел это:
public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector)
{
foreach (T item in enumerable)
{
yield return item;
IEnumerable<T> seqRecurse = recursivePropertySelector(item);
if (seqRecurse == null) continue;
foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector))
{
yield return itemRecurse;
}
}
}
Теоретически это выглядит хорошо, но на практике я обнаружил, что он работает значительно хуже, чем использование эквивалентного рукописного кода (при возникновении ситуации) для прохождения графа и выполнения всего, что нужно сделать. Я подозреваю, что это связано с тем, что в этом методе для каждого элемента, который он возвращает, стек должен развернуться до некоторого произвольно глубокого уровня.
Я также подозреваю, что этот метод будет работать намного эффективнее, если рекурсия будет устранена. Я также не очень хорош в устранении рекурсии.
Кто-нибудь знает, как переписать этот метод, чтобы устранить рекурсию?
Спасибо за любую помощь.
РЕДАКТИРОВАТЬ: Большое спасибо за все подробные ответы. Я попытался сравнить исходное решение с решением Эрика, не используя метод перечислителя и вместо этого рекурсивно обходить с помощью лямбды и, как ни странно, лямбда-рекурсия значительно быстрее, чем любой из двух других методов.
class Node
{
public List<Node> ChildNodes { get; set; }
public Node()
{
ChildNodes = new List<Node>();
}
}
class Foo
{
public static void Main(String[] args)
{
var nodes = new List<Node>();
for(int i = 0; i < 100; i++)
{
var nodeA = new Node();
nodes.Add(nodeA);
for (int j = 0; j < 100; j++)
{
var nodeB = new Node();
nodeA.ChildNodes.Add(nodeB);
for (int k = 0; k < 100; k++)
{
var nodeC = new Node();
nodeB.ChildNodes.Add(nodeC);
for(int l = 0; l < 12; l++)
{
var nodeD = new Node();
nodeC.ChildNodes.Add(nodeD);
}
}
}
}
nodes.TraverseOld(node => node.ChildNodes).ToList();
nodes.TraverseNew(node => node.ChildNodes).ToList();
var watch = Stopwatch.StartNew();
nodes.TraverseOld(node => node.ChildNodes).ToList();
watch.Stop();
var recursiveTraversalTime = watch.ElapsedMilliseconds;
watch.Restart();
nodes.TraverseNew(node => node.ChildNodes).ToList();
watch.Stop();
var noRecursionTraversalTime = watch.ElapsedMilliseconds;
Action<Node> visitNode = null;
visitNode = node =>
{
foreach (var child in node.ChildNodes)
visitNode(child);
};
watch.Restart();
foreach(var node in nodes)
visitNode(node);
watch.Stop();
var lambdaRecursionTime = watch.ElapsedMilliseconds;
}
}
Где TraverseOld - оригинальный метод, TraverseNew - метод Эрика, и, очевидно, лямбда - это лямбда.
На моей машине TraverseOld занимает 10127 мс, TraverseNew - 3038 мс, лямбда-рекурсия - 1181 мс.
Типично ли, что методы перечислителя (с возвращаемым доходом) могут занимать 3 раза дольше, чем немедленное выполнение? Или здесь что-то еще происходит?
4 ответа
Во-первых, вы абсолютно правы; если в графе имеется n узлов средней глубины d, то наивные вложенные итераторы дают решение, которое по времени равно O(n*d), а по стеку - O(d). Если d - большая доля n, то это может стать алгоритмом O (n2), а если d велико, то вы можете полностью удалить стек.
Если вы заинтересованы в анализе производительности вложенных итераторов, посмотрите сообщение в блоге бывшего разработчика компилятора C# Уэса Дайера:
http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx
Решение dasblinkenlight - это вариант стандартного подхода. Я бы обычно писал программу так:
public static IEnumerable<T> Traverse<T>(
T root,
Func<T, IEnumerable<T>> children)
{
var stack = new Stack<T>();
stack.Push(root);
while(stack.Count != 0)
{
T item = stack.Pop();
yield return item;
foreach(var child in children(item))
stack.Push(child);
}
}
И тогда, если у вас есть несколько корней:
public static IEnumerable<T> Traverse<T>(
IEnumerable<T> roots,
Func<T, IEnumerable<T>> children)
{
return from root in roots
from item in Traverse(root, children)
select item ;
}
Теперь обратите внимание, что обход не то, что вы хотите, если у вас есть сильно взаимосвязанный граф или циклический граф! Если у вас есть график со стрелками, указывающими вниз:
A
/ \
B-->C
\ /
D
тогда обход A, B, D, C, D, C, D. Если у вас есть циклический или взаимосвязанный граф, то вам нужно транзитивное замыкание.
public static IEnumerable<T> Closure<T>(
T root,
Func<T, IEnumerable<T>> children)
{
var seen = new HashSet<T>();
var stack = new Stack<T>();
stack.Push(root);
while(stack.Count != 0)
{
T item = stack.Pop();
if (seen.Contains(item))
continue;
seen.Add(item);
yield return item;
foreach(var child in children(item))
stack.Push(child);
}
}
Этот вариант дает только те предметы, которые не были получены ранее.
Я также не очень хорош в устранении рекурсии.
Я написал ряд статей о способах устранения рекурсии и о рекурсивном программировании в целом. Если эта тема вас интересует, смотрите:
http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/
Особенно:
Вы правы, ходя по деревьям и графикам рекурсивно в коде, который делает yield return
это большой источник неэффективности.
Как правило, вы переписываете рекурсивный код со стеком - аналогично тому, как это обычно реализуется в скомпилированном коде.
Я не получил шанс попробовать это, но это должно работать:
public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) {
var stack = new Stack<IEnumerable<T>>();
stack.Push(enumerable);
while (stack.Count != 0) {
enumerable = stack.Pop();
foreach (T item in enumerable) {
yield return item;
var seqRecurse = recursivePropertySelector(item);
if (seqRecurse != null) {
stack.Push(seqRecurse);
}
}
}
}
Вы всегда можете устранить рекурсию, воспроизведя основы работы рекурсии со стеком.
- поместите первый предмет на вершину стека
- Пока стек не пуст, вытолкнуть предмет из стека
- если у текущего узла есть дети, добавьте их в стек
- Урожай возвращает текущий товар.
- Переходите к шагу 1!
Сумасшедший умный теоретический ответ: /questions/8246522/mozhet-li-kazhdaya-rekursiya-byit-preobrazovana-v-iteratsiyu/8246551#8246551
http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf
Вы можете использовать очередь в своем коде. Очередь может быть инициализирована как список с одним элементом, равным верхнему узлу. Затем вы должны перебирать каждый элемент списка, начиная с первого. Если первый элемент содержит дочерние узлы, вы добавляете их все в конец очереди. Затем перейдите к следующему элементу. Ваш график будет полностью сплющен, когда вы достигнете конца очереди.