Как сгладить дерево через LINQ?
Итак, у меня есть простое дерево:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
у меня есть IEnumerable<MyNode>, Я хочу получить список всех MyNode (включая объекты внутреннего узла (Elements)) как один плоский список Wheregroup == 1, Как сделать это через LINQ?
16 ответов
Вы можете сгладить дерево следующим образом:
IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) {
return e.SelectMany(c => Flatten(c.Elements)).Concat(new[] {e});
}
Затем вы можете отфильтровать по group с помощью Where(...),
Чтобы заработать "очки за стиль", конвертируйте Flatten к функции расширения в статическом классе.
public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) {
return e.SelectMany(c => c.Elements.Flatten()).Concat(e);
}
Чтобы заработать очки за "еще лучший стиль", конвертируйте Flatten в общий метод расширения, который берет дерево и функцию, которая производит потомков:
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> e,
Func<T,IEnumerable<T>> f)
{
return e.SelectMany(c => f(c).Flatten(f)).Concat(e);
}
Вызовите эту функцию так:
IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);
Если вы предпочитаете выравнивание в предварительном заказе, а не в последующем заказе, переключайтесь по сторонам Concat(...),
Проблема с принятым ответом заключается в том, что он неэффективен, если дерево глубокое. Если дерево очень глубокое, оно уносит стек. Вы можете решить проблему, используя явный стек:
public static IEnumerable<MyNode> Traverse(this MyNode root)
{
var stack = new Stack<MyNode>();
stack.Push(root);
while(stack.Count > 0)
{
var current = stack.Pop();
yield return current;
foreach(var child in current.Elements)
stack.Push(child);
}
}
Предполагая n узлов в дереве высоты h и коэффициент ветвления значительно меньше, чем n, этот метод равен O (1) в пространстве стека, O (h) в пространстве кучи и O (n) во времени. Другой заданный алгоритм - это O (h) в стеке, O (1) в куче и O (nh) во времени. Если коэффициент ветвления мал по сравнению с n, то h находится между O (lg n) и O (n), что показывает, что наивный алгоритм может использовать опасное количество стеков и большое количество времени, если h близко к n.
Теперь, когда у нас есть обход, ваш запрос прост:
root.Traverse().Where(item=>item.group == 1);
Просто для полноты, вот сочетание ответов от dasblinkenlight и Эрика Липперта. Блок проверен и все.:-)
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> items,
Func<T, IEnumerable<T>> getChildren)
{
var stack = new Stack<T>();
foreach(var item in items)
stack.Push(item);
while(stack.Count > 0)
{
var current = stack.Pop();
yield return current;
var children = getChildren(current);
if (children == null) continue;
foreach (var child in children)
stack.Push(child);
}
}
Обновить:
Для людей, интересующихся уровнем вложенности (глубиной). Одна из хороших вещей в явной реализации стека перечислителя заключается в том, что в любой момент (и в частности, при выдаче элемента) stack.Count представляет текущую глубину обработки. Поэтому, принимая это во внимание и используя кортежи значений C#7.0, мы можем просто изменить объявление метода следующим образом:
public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
а также yield заявление:
yield return (item, stack.Count);
Тогда мы можем реализовать оригинальный метод, применяя простой Select на вышеупомянутом:
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
source.ExpandWithLevel(elementSelector).Select(e => e.Item);
Оригинал:
Удивительно, но никто (даже Эрик) не показал "естественный" итеративный порт рекурсивного DFT предварительного заказа, так что вот оно:
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
{
var stack = new Stack<IEnumerator<T>>();
var e = source.GetEnumerator();
try
{
while (true)
{
while (e.MoveNext())
{
var item = e.Current;
yield return item;
var elements = elementSelector(item);
if (elements == null) continue;
stack.Push(e);
e = elements.GetEnumerator();
}
if (stack.Count == 0) break;
e.Dispose();
e = stack.Pop();
}
}
finally
{
e.Dispose();
while (stack.Count != 0) stack.Pop().Dispose();
}
}
Я нашел несколько небольших вопросов с ответами, приведенными здесь:
- Что если начальный список элементов равен нулю?
- Что если в списке детей есть нулевое значение?
Построенный на предыдущих ответах и придумал следующее:
public static class IEnumerableExtensions
{
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> items,
Func<T, IEnumerable<T>> getChildren)
{
if (items == null)
yield break;
var stack = new Stack<T>(items);
while (stack.Count > 0)
{
var current = stack.Pop();
yield return current;
if (current == null) continue;
var children = getChildren(current);
if (children == null) continue;
foreach (var child in children)
stack.Push(child);
}
}
}
И юнит-тесты:
[TestClass]
public class IEnumerableExtensionsTests
{
[TestMethod]
public void NullList()
{
IEnumerable<Test> items = null;
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(0, flattened.Count());
}
[TestMethod]
public void EmptyList()
{
var items = new Test[0];
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(0, flattened.Count());
}
[TestMethod]
public void OneItem()
{
var items = new[] { new Test() };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(1, flattened.Count());
}
[TestMethod]
public void OneItemWithChild()
{
var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(2, flattened.Count());
Assert.IsTrue(flattened.Any(i => i.Id == 1));
Assert.IsTrue(flattened.Any(i => i.Id == 2));
}
[TestMethod]
public void OneItemWithNullChild()
{
var items = new[] { new Test { Id = 1, Children = new Test[] { null } } };
var flattened = items.Flatten(i => i.Children);
Assert.AreEqual(2, flattened.Count());
Assert.IsTrue(flattened.Any(i => i.Id == 1));
Assert.IsTrue(flattened.Any(i => i == null));
}
class Test
{
public int Id { get; set; }
public IEnumerable<Test> Children { get; set; }
}
}
Большинство ответов, представленных здесь, создают последовательности в глубину или зигзагообразные последовательности. Например, начиная с дерева ниже:
1 2
/ \ / \
/ \ / \
/ \ / \
/ \ / \
11 12 21 22
/ \ / \ / \ / \
/ \ / \ / \ / \
111 112 121 122 211 212 221 222
dasblinkenlight в ответ производит эту сплющенную последовательность:
111, 112, 121, 122, 11, 12, 211, 212, 221, 222, 21, 22, 1, 2
Konamiman в ответ (что обобщается Эрик Липперта ответа) производит эту сплюснутую последовательность:
2, 22, 222, 221, 21, 212, 211, 1, 12, 122, 121, 11, 112, 111
Ответ Ивана Стоева дает эту уплощенную последовательность:
1, 11, 111, 112, 12, 121, 122, 2, 21, 211, 212, 22, 221, 222
Если вы заинтересованы в широте первой последовательности, как это:
1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222
... тогда это решение для вас:
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
Func<T, IEnumerable<T>> childrenSelector)
{
var queue = new Queue<T>(source);
while (queue.Count > 0)
{
var current = queue.Dequeue();
yield return current;
var children = childrenSelector(current);
if (children == null) continue;
foreach (var child in children) queue.Enqueue(child);
}
}
Разница в реализации в основном заключается в использовании
Queue вместо
Stack. Фактической сортировки не происходит.
Предупреждение: эта реализация далека от оптимальной с точки зрения эффективности использования памяти, поскольку большой процент от общего числа элементов в конечном итоге будет сохранен во внутренней очереди во время перечисления.
Stackобходы по дереву намного эффективнее с точки зрения использования памяти, чем
Queueреализации на основе.
В случае, если кто-то еще обнаружит это, но также должен знать уровень после того, как он сплющил дерево, это расширяет комбинацию dasblinkenlight и решения Эрика Липперта от Konamiman:
public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(
this IEnumerable<T> items,
Func<T, IEnumerable<T>> getChilds)
{
var stack = new Stack<Tuple<T, int>>();
foreach (var item in items)
stack.Push(new Tuple<T, int>(item, 1));
while (stack.Count > 0)
{
var current = stack.Pop();
yield return current;
foreach (var child in getChilds(current.Item1))
stack.Push(new Tuple<T, int>(child, current.Item2 + 1));
}
}
Другой вариант - создать правильный объектно-ориентированный дизайн.
например, спросите MyNode вернуть все ровно.
Как это:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
public IEnumerable<MyNode> GetAllNodes()
{
if (Elements == null)
{
return Enumerable.Empty<MyNode>();
}
return Elements.SelectMany(e => e.GetAllNodes());
}
}
Теперь вы можете попросить MyNode верхнего уровня получить все узлы.
var flatten = topNode.GetAllNodes();
Если вы не можете редактировать класс, тогда это не вариант. Но в противном случае я думаю, что это может быть предпочтительнее отдельного (рекурсивного) метода LINQ.
Здесь используется LINQ, поэтому я думаю, что этот ответ применим здесь;)
Самый простой / понятный способ решить эту проблему - использовать рекурсивный запрос LINQ. Этот вопрос: Выражение рекурсии в LINQ имеет много дискуссий по этому вопросу, и этот конкретный ответ /questions/16958816/vyirazhenie-rekursii-v-linq/16958835#16958835 посвящен некоторым подробностям того, как вы бы это реализовали.
Вот несколько готовых к использованию реализаций, использующих Queue и возвращающих дерево Flatten сначала мне, а затем моим детям.
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> items,
Func<T,IEnumerable<T>> getChildren)
{
if (items == null)
yield break;
var queue = new Queue<T>();
foreach (var item in items) {
if (item == null)
continue;
queue.Enqueue(item);
while (queue.Count > 0) {
var current = queue.Dequeue();
yield return current;
if (current == null)
continue;
var children = getChildren(current);
if (children == null)
continue;
foreach (var child in children)
queue.Enqueue(child);
}
}
}
Комбинируя ответ Дейва и Ивана Стоева на тот случай, если вам нужен уровень вложенности и список выровнен "по порядку" и не перевернут, как в ответе, который дал Конамиман.
public static class HierarchicalEnumerableUtils
{
private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level)
{
if (source == null)
{
return null;
}
else
{
return source.Select(item => new Tuple<T, int>(item, level));
}
}
public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
{
var stack = new Stack<IEnumerator<Tuple<T, int>>>();
var leveledSource = source.ToLeveled(0);
var e = leveledSource.GetEnumerator();
try
{
while (true)
{
while (e.MoveNext())
{
var item = e.Current;
yield return item;
var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1);
if (elements == null) continue;
stack.Push(e);
e = elements.GetEnumerator();
}
if (stack.Count == 0) break;
e.Dispose();
e = stack.Pop();
}
}
finally
{
e.Dispose();
while (stack.Count != 0) stack.Pop().Dispose();
}
}
}
На основе предыдущего ответа
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> e
, Func<T, IEnumerable<T>> f
) => e.Concat(e.SelectMany(c => f(c).Flatten(f)));
Ниже приведен код Ивана Стоева с дополнительной функцией определения индекса каждого объекта в пути. Например, поиск "Item_120":
Item_0--Item_00
Item_01
Item_1--Item_10
Item_11
Item_12--Item_120
вернет элемент и массив int [1,2,0]. Очевидно, что уровень вложенности также доступен, как длина массива.
public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
var stack = new Stack<IEnumerator<T>>();
var e = source.GetEnumerator();
List<int> indexes = new List<int>() { -1 };
try {
while (true) {
while (e.MoveNext()) {
var item = e.Current;
indexes[stack.Count]++;
yield return (item, indexes.Take(stack.Count + 1).ToArray());
var elements = getChildren(item);
if (elements == null) continue;
stack.Push(e);
e = elements.GetEnumerator();
if (indexes.Count == stack.Count)
indexes.Add(-1);
}
if (stack.Count == 0) break;
e.Dispose();
indexes[stack.Count] = -1;
e = stack.Pop();
}
} finally {
e.Dispose();
while (stack.Count != 0) stack.Pop().Dispose();
}
}
Основываясь на ответе Konamiman и комментарии о том, что упорядочение является неожиданным, вот версия с явным параметром сортировки:
public static IEnumerable<T> TraverseAndFlatten<T, V>(this IEnumerable<T> items, Func<T, IEnumerable<T>> nested, Func<T, V> orderBy)
{
var stack = new Stack<T>();
foreach (var item in items.OrderBy(orderBy))
stack.Push(item);
while (stack.Count > 0)
{
var current = stack.Pop();
yield return current;
var children = nested(current).OrderBy(orderBy);
if (children == null) continue;
foreach (var child in children)
stack.Push(child);
}
}
И пример использования:
var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList();
void Main()
{
var allNodes = GetTreeNodes().Flatten(x => x.Elements);
allNodes.Dump();
}
public static class ExtensionMethods
{
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector = null)
{
if (source == null)
{
return new List<T>();
}
var list = source;
if (childrenSelector != null)
{
foreach (var item in source)
{
list = list.Concat(childrenSelector(item).Flatten(childrenSelector));
}
}
return list;
}
}
IEnumerable<MyNode> GetTreeNodes() {
return new[] {
new MyNode { Elements = new[] { new MyNode() }},
new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }}
};
}
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
Время от времени я пытаюсь поцарапать эту проблему и разработать собственное решение, которое поддерживает сколь угодно глубокие структуры (без рекурсии), выполняет обход в ширину и не злоупотребляет слишком большим количеством запросов LINQ и не выполняет превентивную рекурсию для детей. Покопавшись в исходном коде.NET и попробовав множество решений, я наконец нашел это решение. В итоге он оказался очень близок к ответу Яна Стоева (ответ которого я только что видел), однако мой не использует бесконечные циклы или не имеет необычного потока кода.
public static IEnumerable<T> Traverse<T>(
this IEnumerable<T> source,
Func<T, IEnumerable<T>> fnRecurse)
{
if (source != null)
{
Stack<IEnumerator<T>> enumerators = new Stack<IEnumerator<T>>();
try
{
enumerators.Push(source.GetEnumerator());
while (enumerators.Count > 0)
{
var top = enumerators.Peek();
while (top.MoveNext())
{
yield return top.Current;
var children = fnRecurse(top.Current);
if (children != null)
{
top = children.GetEnumerator();
enumerators.Push(top);
}
}
enumerators.Pop().Dispose();
}
}
finally
{
while (enumerators.Count > 0)
enumerators.Pop().Dispose();
}
}
}
Рабочий пример можно найти здесь.