그래서 간단한 트리가 있습니다.
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
나는 IEnumerable<MyNode>. 나는 모든 MyNode(내부 노드 객체 ( Elements) 포함) 목록을 하나의 플랫 목록 으로 얻고 싶습니다 Where group == 1. LINQ를 통해 이러한 작업을 수행하는 방법은 무엇입니까?
답변
다음과 같이 나무를 평평하게 만들 수 있습니다.
IEnumerable<MyNode> Flatten(IEnumerable<MyNode> e) =>
e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });
그런 다음을 group사용하여 필터링 할 수 있습니다 Where(...).
“스타일 점수”를 얻으려면 Flatten정적 클래스의 확장 함수 로 변환하십시오 .
public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
e.SelectMany(c => c.Elements.Flatten()).Concat(e);
“더 나은 스타일”에 대해 더 많은 포인트를 얻으려면 Flatten트리와 노드에서 자손을 생성하는 함수를 사용하는 일반 확장 메소드 로 변환 하십시오.
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> e
, Func<T,IEnumerable<T>> f
) => 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);
}
}
높이가 h 인 트리에서 n 개 노드와 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와 Eric Lippert의 답변 조합이 있습니다. 단위 테스트 및 모든 것. 🙂
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);
실물:
놀랍게도 아무도 (심지어 Eric) 재귀 적 선주문 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();
}
}
답변
여기에 제공된 답변에서 몇 가지 작은 문제를 발견했습니다.
- 초기 항목 목록이 null이면 어떻게됩니까?
- 자식 목록에 null 값이 있으면 어떻게됩니까?
이전 답변을 바탕으로 다음을 생각해 냈습니다.
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; }
}
}답변
다른 사람이 이것을 찾았지만 나무를 평평하게 한 후에 레벨을 알아야 할 경우, Konamiman의 dasblinkenlight와 Eric Lippert의 솔루션 조합이 확장됩니다.
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));
}
}답변
정말 다른 옵션은 적절한 OO 디자인을 갖는 것입니다.
예를 들어 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를 사용하고 있으므로이 답변이 여기에 적용 가능하다고 생각합니다.)
