Как “развернуть” “рекурсивную” структуру
Не уверенный, как назвать его, но сказать, у Вас есть класс, который похож на это:
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);
4 ответа
] Я не верю, что есть что-то встроенное в LINQ, чтобы сделать это. [
] [] Есть проблема с тем, чтобы делать это рекурсивно - в конечном итоге вы создаете большое количество итераторов. Это может быть довольно неэффективно, если дерево глубоко. []Wes Dyer[] и []Eric Lippert[] оба писали об этом в блоге.[
] []Вы можете устранить эту неэффективность, удалив прямую рекурсию. Например:[
] [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), то вы будете повторять их навсегда.[
].]Также можно использовать не рекурсивный метод, как этот:[
] [ 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;
}
]Он также должен корректно обрабатывать циклы. Я []am[] начинаю с одного человека, но вы можете легко расширить его, чтобы начать со списка людей. [
]]Recursion - это всегда весело. Возможно, вы могли бы упростить свой код до:[
] [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);
}
]Это приведет к меньшему количеству дубликатов, чем ваш исходный код. Однако их дубликаты все равно могут привести к бесконечному циклу, объединение предотвратит только прямые дубликаты родителя(ов) -ребенка(ов).[
] []И порядок элементов будет отличаться от вашего :)[
] [][]Правка:[] Изменена последняя строка кода на три утверждения и добавлена немного больше документации.[
]используйте расширение 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;
}