Любой способ сделать эту рекурсивную функцию лучше/быстрее?


Есть все, что может быть сделано по-разному для этой функции? Любой способ сделать это быстрее?

public List<Channel> ChildrenOf(Channel startingChannel)
{
    List<Channel> result = new List<Channel>();

    foreach (Channel child in startingChannel.Children)
    {
        result.Add(child);
        result.AddRange(ChildrenOf(child));
    }

    return result;
}


18298
19
задан 28 октября 2011 в 07:10 Источник Поделиться
Комментарии
4 ответа

Я бы отдельную итерацию и добавлять элементы в список:

public IEnumerable<Channel> ChildrenOf(Channel root)
{
yield return root;
foreach(var c in root.Children)
foreach(var cc in ChildrenOf(c))
yield return cc;
}

13
ответ дан 28 октября 2011 в 07:10 Источник Поделиться

Просто чтобы закруглить другие ответы: я был бы склонен написать свое решение так:

static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)      
{
var stack = new Stack<T>();
stack.Push(root);
while(stack.Count != 0)
{
var current = stack.Pop();
// If you don't care about maintaining child order then remove the Reverse.
foreach(var child in children(current).Reverse())
stack.Push(child);
yield return current;
}
}

И теперь, чтобы достичь своей цели, вы просто говорите:

    static List<Channel> AllChildren(Channel start)
{
return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
}

Теперь у вас есть более универсальный инструмент, который можно использовать, чтобы получить глубину обхода любое дерево структуры, а не только конкретной структуры.

Еще одна приятная особенность моего решения в том, что он использует фиксированный размер стека вызовов пространства. Даже если ваша иерархия двадцать тысяч глубоко, вы никогда не бежите из стека, потому что метод не является рекурсивным для начала. Вся информация, которая будет необходима для рекурсии хранится на "стек" структуры данных, а не в записи активации в стеке вызовов в режиме реального.

39
ответ дан 28 октября 2011 в 01:10 Источник Поделиться

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

public List<Channel> ChildrenOf(Channel startingChannel) {
List<Channel> result = new List<Channel>();
AddChildren(startingChannel, result);
return result;
}

private void AddChildren(Channel channel, List<Channel> list) {
foreach (Channel child in channel.Children) {
list.Add(child);
AddChildren(child, list);
}
}

(Это в основном тот же принцип, что государства предложил, только он реализован двумя способами, так что вы не должны создать пустой список это назвать.)

16
ответ дан 28 октября 2011 в 07:10 Источник Поделиться

Поделитесь своими список получился бы один из способов предотвращения выделений и коллекции так случиться

 public List<Channel> ChildrenOf(Channel startingChannel, List<Channel> result) 
{
foreach (Channel child in startingChannel.Children)
{
result.Add(child);

// this will internally add to result
ChildrenOf(child, result);
}

return result;
}

11
ответ дан 28 октября 2011 в 07:10 Источник Поделиться