Как "развернуть" "рекурсивную" структуру
Не уверен, как это назвать, но скажите, что у вас есть класс, который выглядит так:
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);
Ответы
Ответ 1
Я не верю, что в LINQ ничего не было сделано для этого.
Есть проблема с рекурсивно подобным образом: вы создаете большое количество итераторов. Это может быть весьма неэффективно, если дерево глубокое. Wes Dyer и Эрик Липперт об этом сообщают в блоге.
Вы можете удалить эту неэффективность, удалив прямую рекурсию. Например:
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() - эта пересмотренная версия не будет оценивать какую-либо последовательность более одного раза, что может быть удобно в некоторых сценариях. У вас есть одна проблема, заметьте - это займет больше памяти из-за очереди. Вероятно, мы могли бы облегчить это, сохранив очередь итераторов вместо элементов, но я не уверен, что это было бы глупо.
Одно замечание (также отмечено ChrisW, когда я смотрел сообщения в блоге:) - если у вас есть какие-то циклы в списке ваших друзей (т.е. если A имеет B, а B - A), вы будете навсегда.
Ответ 2
Я нашел этот вопрос так, как я искал и думал о подобном решении - в моем случае создал эффективный элемент управления IEnumerable<Control> для ASP.NET UI. Рекурсивный yield у меня был быстрый, но я знал, что это может иметь дополнительные затраты, поскольку чем глубже структура управления, тем дольше это может потребоваться. Теперь я знаю, что это O (n log n).
Решение, приведенное здесь, дает некоторый ответ, но, как обсуждалось в комментариях, он меняет порядок (который OP не заботился). Я понял, что для сохранения порядка, заданного OP, и, как мне было нужно, ни простой Queue (как использовал Джон), ни Stack не будут работать, поскольку все родительские объекты будут уступать первым, а затем любые дети после них ( или наоборот).
Чтобы решить эту проблему и сохранить заказ, я понял, что решение просто состоит в том, чтобы поставить Enumerator на Stack. Чтобы использовать исходный вопрос OPs, он будет выглядеть следующим образом:
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 для дочерних счетчиков до текущей глубины в стеке рекурсии).
Ответ 3
используйте расширение 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;
}
Ответ 4
Здесь реализована реализация, которая:
- Определяет глубину первого рекурсивного выбора,
- Не требует двойной итерации дочерних коллекций,
- Не использует промежуточные коллекции для выбранных элементов,
- Не обрабатывает циклы,
-
Можно сделать это назад.
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();
}
}
}
Ответ 5
Вы также можете использовать нерекурсивный метод:
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;
}
Это должно также правильно обрабатывать циклы. Я начинаю с одного человека, но вы можете легко расширить его, чтобы начать со списка людей.
Ответ 6
Рекурсия всегда интересна. Возможно, вы могли бы упростить свой код:
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);
}
Это приведет к меньшему количеству дубликатов, чем ваш исходный код. Однако их по-прежнему могут быть дубликаты, вызывающие бесконечный цикл, объединение будет только предотвращать дублирование прямых родительских (-ых) символов.
И порядок элементов будет отличаться от вашего:)
Изменить: Изменена последняя строка кода для трех операторов и добавлена немного больше документации.
