Как "развернуть" "рекурсивную" структуру
Не уверен, как это назвать, но скажем, у вас есть класс, который выглядит так:
class Person
{
public string Name;
public IEnumerable<Person> Friends;
}
Затем у вас есть человек, и вы хотите рекурсивно "развернуть" эту структуру, чтобы вы получили единый список всех людей без дубликатов.
Как бы вы это сделали? Я уже сделал что-то, что, кажется, работает, но мне любопытно посмотреть, как это сделают другие, особенно если в Linq есть что-то встроенное, что вы можете использовать умным способом для решения этой маленькой проблемы:)
Вот мое решение:
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
// Stop if subjects are null or empty
if(subjects == null)
yield break;
// For each subject
foreach(var subject in subjects)
{
// Yield it
yield return subject;
// Then yield all its decendants
foreach (var decendant in SelectRecursive(selector(subject), selector))
yield return decendant;
}
}
Будет использоваться что-то вроде этого:
var people = somePerson.SelectRecursive(x => x.Friends);
7 ответов
Я не верю, что в LINQ есть что-то для этого.
Существует проблема с рекурсивным выполнением этого - в итоге вы создаете большое количество итераторов. Это может быть совершенно неэффективно, если дерево глубоко. Уэс Дайер и Эрик Липперт писали об этом в блоге.
Вы можете устранить эту неэффективность, удалив прямую рекурсию. Например:
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
Func<T, IEnumerable<T>> selector)
{
if (subjects == null)
{
yield break;
}
Queue<T> stillToProcess = new Queue<T>(subjects);
while (stillToProcess.Count > 0)
{
T item = stillToProcess.Dequeue();
yield return item;
foreach (T child in selector(item))
{
stillToProcess.Enqueue(child);
}
}
}
Это также изменит порядок итераций - он становится шириной, а не глубиной; переписать его так, чтобы он все еще был первым, сложно. Я также изменил это, чтобы не использовать Any() - эта пересмотренная версия не будет оценивать последовательность более одного раза, что может быть полезно в некоторых сценариях. Имейте в виду, есть одна проблема - из-за очередей потребуется больше памяти. Мы могли бы, вероятно, смягчить это, сохранив очередь итераторов вместо элементов, но я не уверен, что это было бы необоснованно... это, безусловно, было бы более сложным.
Одно замечание (также отмеченное ChrisWe, когда я просматривал сообщения в блоге:) - если у вас есть какие-либо циклы в списке друзей (то есть, если у A есть B, а у B есть A), вы будете возвращаться навсегда.
Я нашел этот вопрос, когда искал и думал о подобном решении - в моем случае создание эффективного IEnumerable<Control> для элементов управления ASP.NET UI. Рекурсивный yield У меня было быстро, но я знал, что это может привести к дополнительным затратам, поскольку чем глубже структура управления, тем дольше это может занять. Теперь я знаю, что это O(n log n).
Решение, приведенное здесь, дает некоторый ответ, но, как обсуждалось в комментариях, оно меняет порядок (который ОП не заботил). Я понял, что для сохранения порядка, заданного ФП и, как мне было нужно, ни Queue (как использовал Джон) ни Stack будет работать, так как сначала будут получены все родительские объекты, а затем любые дочерние объекты после них (или наоборот).
Чтобы решить эту проблему и сохранить порядок, я понял, что решение будет просто положить Enumerator сам на Stack, Если использовать оригинальный вопрос ОП, это будет выглядеть так:
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
if (subjects == null)
yield break;
var stack = new Stack<IEnumerator<T>>();
stack.Push(subjects.GetEnumerator());
while (stack.Count > 0)
{
var en = stack.Peek();
if (en.MoveNext())
{
var subject = en.Current;
yield return subject;
stack.Push(selector(subject).GetEnumerator());
}
else
{
stack.Pop();
}
}
}
я использую stack.Peek здесь, чтобы избежать необходимости помещать один и тот же перечислитель обратно в стек, так как это, вероятно, будет более частой операцией, ожидая, что перечислитель предоставит более одного элемента.
Это создает то же число перечислителей, что и в рекурсивной версии, но, вероятно, будет меньше новых объектов, чем помещение всех объектов в очередь или стек и продолжение добавления любых объектов-потомков. Это время O(n), так как каждый перечислитель стоит сам по себе (в рекурсивной версии неявный вызов одного MoveNext исполняет MoveNext на дочерних перечислителях до текущей глубины в стеке рекурсии).
Вы также можете использовать нерекурсивный метод, подобный этому:
HashSet<Person> GatherAll (Person p) {
Stack<Person> todo = new Stack<Person> ();
HashSet<Person> results = new HashSet<Person> ();
todo.Add (p); results.Add (p);
while (todo.Count > 0) {
Person p = todo.Pop ();
foreach (Person f in p.Friends)
if (results.Add (f)) todo.Add (f);
}
return results;
}
Это должно правильно обрабатывать циклы. Я начинаю с одного человека, но вы можете легко расширить это, чтобы начать со списка людей.
Вот реализация, которая:
- Есть ли рекурсивный выбор глубины,
- Не требует двойной итерации дочерних коллекций,
- Не использует промежуточные коллекции для выбранных элементов,
- Не обрабатывает циклы,
Можно сделать это задом наперед.
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector) { return new RecursiveEnumerable<T>(rootItems, selector, false); } public static IEnumerable<T> SelectRecursiveReverse<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector) { return new RecursiveEnumerable<T>(rootItems, selector, true); } class RecursiveEnumerable<T> : IEnumerable<T> { public RecursiveEnumerable(IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector, bool reverse) { _rootItems = rootItems; _selector = selector; _reverse = reverse; } IEnumerable<T> _rootItems; Func<T, IEnumerable<T>> _selector; bool _reverse; public IEnumerator<T> GetEnumerator() { return new Enumerator(this); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } class Enumerator : IEnumerator<T> { public Enumerator(RecursiveEnumerable<T> owner) { _owner = owner; Reset(); } RecursiveEnumerable<T> _owner; T _current; Stack<IEnumerator<T>> _stack = new Stack<IEnumerator<T>>(); public T Current { get { if (_stack == null || _stack.Count == 0) throw new InvalidOperationException(); return _current; } } public void Dispose() { _current = default(T); if (_stack != null) { while (_stack.Count > 0) { _stack.Pop().Dispose(); } _stack = null; } } object System.Collections.IEnumerator.Current { get { return Current; } } public bool MoveNext() { if (_owner._reverse) return MoveReverse(); else return MoveForward(); } public bool MoveForward() { // First time? if (_stack == null) { // Setup stack _stack = new Stack<IEnumerator<T>>(); // Start with the root items _stack.Push(_owner._rootItems.GetEnumerator()); } // Process enumerators on the stack while (_stack.Count > 0) { // Get the current one var se = _stack.Peek(); // Next please... if (se.MoveNext()) { // Store it _current = se.Current; // Get child items var childItems = _owner._selector(_current); if (childItems != null) { _stack.Push(childItems.GetEnumerator()); } return true; } // Finished with the enumerator se.Dispose(); _stack.Pop(); } // Finished! return false; } public bool MoveReverse() { // First time? if (_stack == null) { // Setup stack _stack = new Stack<IEnumerator<T>>(); // Start with the root items _stack.Push(_owner._rootItems.Reverse().GetEnumerator()); } // Process enumerators on the stack while (_stack.Count > 0) { // Get the current one var se = _stack.Peek(); // Next please... if (se.MoveNext()) { // Get child items var childItems = _owner._selector(se.Current); if (childItems != null) { _stack.Push(childItems.Reverse().GetEnumerator()); continue; } // Store it _current = se.Current; return true; } // Finished with the enumerator se.Dispose(); _stack.Pop(); if (_stack.Count > 0) { _current = _stack.Peek().Current; return true; } } // Finished! return false; } public void Reset() { Dispose(); } } }
Рекурсия это всегда весело. Возможно, вы могли бы упростить свой код до:
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector) {
// Stop if subjects are null or empty
if (subjects == null || !subjects.Any())
return Enumerable.Empty<T>();
// Gather a list of all (selected) child elements of all subjects
var subjectChildren = subjects.SelectMany(selector);
// Jump into the recursion for each of the child elements
var recursiveChildren = SelectRecursive(subjectChildren, selector);
// Combine the subjects with all of their (recursive child elements).
// The union will remove any direct parent-child duplicates.
// Endless loops due to circular references are however still possible.
return subjects.Union(recursiveChildren);
}
Это приведет к меньшему количеству дубликатов, чем ваш исходный код. Однако они могут быть дубликатами, вызывающими бесконечный цикл, объединение будет предотвращать только прямые дубликаты parent(s)-child(s).
И порядок вещей будет отличаться от вашего:)
Изменить: изменил последнюю строку кода на три оператора и добавил немного больше документации.
Используйте расширение Aggregate...
List<Person> persons = GetPersons();
List<Person> result = new List<Person>();
persons.Aggregate(result,SomeFunc);
private static List<Person> SomeFunc(List<Person> arg1,Person arg2)
{
arg1.Add(arg2)
arg1.AddRange(arg2.Persons);
return arg1;
}
Хотя здорово иметь IEnumerable, когда может быть много данных, стоит помнить о классическом подходе рекурсивного добавления в список.
Это может быть так же просто, как это (я пропустил селектор, просто демонстрируя рекурсивное добавление в выходной список):
class Node
{
public readonly List<Node> Children = new List<Node>();
public List<Node> Flatten()
{
var all = new List<Node>();
Flatten(ref all);
return all;
}
public void Flatten(ref List<Node> all)
{
all.Add(this);
foreach (var child in Children)
child.Flatten(ref all);
}
}
Применение:
Node rootNode = ...;
...
var all = rootNode.Flatten();