LINQ를 사용하여 트리 데이터 구조에서 레벨을 얻는 가장 좋은 방법은 무엇입니까?

Question

이제이 컬렉션의 각 노드에 대해 level를 얻으 려합니다. 다음 코드로 시도했지만 가장 좋은지 궁금합니다. 그것을 구현하는 방법.

Func<int, int> GetLevel = (nodeID) => 
{ 
    int _level = 0; 
    var _node = source.First(p => p.Id == nodeID); 

    // while hasn't reached the root yet 
    while (_node .ParentID.HasValue) 
    { 
     _level++; 
     _node = source.First(p => p.Id == _node.ParentID); 
    } 
    return _level; 
}; 

// source is a collection of Node. 

var query = from node in source 
       select new 
       { 
        Id = node.Id, 
        Name = node.Name, 
        ParentID = node.ParentID, 
        Level = GetLevel(node.Id) 
       }; 

GetLevel 함수의 오버 헤드가 줄어들 수 있다고 생각합니다. 아니면이 기능없이 직접 가져 오는 것이 더 좋은 방법 일 것입니다!

어떤 생각이든!

Answer 1

이렇게하면 Node class으로 쉽게 처리 할 수 ​​있습니다.

public class Subject 
{ 
    public int Id { get; set; } 
    public int? ParentId { get; set; } 
    public string Name { get; set; } 
} 

트리를 만들고 각 노드의 수준을 보여

var list = new List<Subject> 
{ 
    new Subject {Id = 0, ParentId = null, Name = "A"}, 
    new Subject {Id = 1, ParentId = 0, Name = "B"}, 
    new Subject {Id = 2, ParentId = 1, Name = "C"}, 
    new Subject {Id = 3, ParentId = 1, Name = "D"}, 
    new Subject {Id = 4, ParentId = 2, Name = "E"}, 
    new Subject {Id = 5, ParentId = 3, Name = "F"}, 
    new Subject {Id = 6, ParentId = 0, Name = "G"}, 
    new Subject {Id = 7, ParentId = 4, Name = "H"}, 
    new Subject {Id = 8, ParentId = 3, Name = "I"}, 
}; 
var rootNode = Node<Subject>.CreateTree(list, n => n.Id, n => n.ParentId).Single(); 

foreach (var node in rootNode.All) 
{ 
    Console.WriteLine("Name {0} , Level {1}", node.Value.Name, node.Level); 
} 

Answer 2

지금은 여러 번 여러 번 처리하고 있습니다. 나는 재귀 적으로 레벨을 만들 것이다. 이렇게하면 처리 오버 헤드가 없습니다.

또한이 기능을 많이 실행하면 노드를 추가 할 때 자동으로 계산되는 변수로 노드 클래스의 수준을 넣을 수 있습니다.

소스 코드가 있습니다.

Answer 3

너비 1 차 순회로 n 걸음을 위에서 아래로 할 수 있습니다. 내가 볼 수있는 한 당신의 접근 방식은 n*log(n)입니까?

빠른 Level 필드

class Node 
{ 
    public string Id; 
    public string ParentID; 
    public int Level; 
    public Node SetLevel(int i) 
    { 
     Level = i; 
     return this; 
    } 
} 

void Main() 
{ 
    var source = new List<Node>(){ 
    new Node(){ Id = "1" }, 
    new Node(){ Id = "2", ParentID="1"}, 
    new Node(){ Id = "3", ParentID="1"}, 
    new Node(){ Id = "4", ParentID="2"} 
    }; 

    var queue = source.Where(p => p.ParentID == null).Select(s => s.SetLevel(0)).ToList(); 
    var cur = 0; 

    while (queue.Any()) 
    { 
     var n = queue[0]; 
     queue.AddRange(source.Where(p => p.ParentID == n.Id).Select(s => s.SetLevel(n.Level + 1))); 
     queue.RemoveAt(0); 
    } 
    source.Dump(); 
} 

출력을 노드 클래스 LinqPad에서 해킹 :

Id ParentID Level 
1 null  0 
2 1  1 
3 1  1 
4 2  2 

그러나이 모두는 Linq에 부품의 복잡성에 따라 달라집니다 (어디에요)

Answer 4

.ToDictionary을 다음과 같이 사용하십시오.

var dictionary = 
    source.ToDictionary(n => n.Id, n => n.ParentId); 

Func<int, int> GetLevel = nid => 
{ 
    var level = -1; 
    if (dictionary.ContainsKey(nid)) 
    { 
     level = 0; 
     var pid = dictionary[nid]; 
     while (pid.HasValue) 
     { 
      level++; 
      pid = dictionary[pid.Value]; 
     } 
    } 
    return level; 
}; 

이것은 최종 쿼리가 모든 노드에서 재귀 될 것이므로 매우 효율적입니다. 따라서 사전을 작성하는 비용은 저렴합니다.

노드의 깊이에 따라 어떤 경우에도 다단계 무차별 강제 검색보다 사전 작성이 빠르다는 것을 알 수 있습니다. 당신은 당신이 이 컬렉션의 각 노드의 레벨을 얻기 위해 필요하다고 때문에

Answer 5

, 당신은 같은 수준 열심히에 노드에서지도를 생성 할 수 있습니다.

적절한 너비 우선 탐색을 사용하여 O (n) 시간에 수행 할 수 있습니다.

(테스트되지 않은) :

public static Dictionary<Node, int> GetLevelsForNodes(IEnumerable<Node> nodes) 
{ 
    //argument-checking omitted. 

    // Thankfully, lookup accepts null-keys. 
    var nodesByParentId = nodes.ToLookup(n => n.ParentID); 

    var levelsForNodes = new Dictionary<Node, int>(); 

    // Singleton list comprising the root. 
    var nodesToProcess = nodesByParentId[null].ToList(); 

    int currentLevel = 0; 

    while (nodesToProcess.Any()) 
    { 
     foreach (var node in nodesToProcess) 
      levelsForNodes.Add(node, currentLevel); 

     nodesToProcess = nodesToProcess.SelectMany(n => nodesByParentId[n.Id]) 
             .ToList(); 
     currentLevel++; 
    } 

    return levelsForNodes; 
} 

Answer 6

내 테스트를 위해 단순화 된 데이터 구조를 사용하고 평평하게 모든 노드의 IEnumerable을 < 트리>에서를 반환주의 아래 무슨 일을하는지의 컴팩트 버전, 아래의 변수 트리에서 트리. 나는 당신이 그 소스에 접근 할 수 있다면 트리 클래스의 재귀 깊이 함수를 만들 것이다.이 작업을 자주하거나 나무가 거대한 경우 (또는 둘 다) 사전이나 트리 구조 자체의 깊이를 캐싱하는 방법에 특히주의해야합니다. 자주하지 않으면 정상적으로 작동합니다. GUI에서 상대적으로 작은 나무 구조를 통과하는 데이 도구를 사용합니다. 아무도 작동이 느린 적이 없다고 생각한 적이 없습니다. 복잡도는 모든 노드의 깊이를 얻기위한 O (N log N) 평균 사례입니다. 모든 코드를보고 싶으면 내일에 넣을 수 있습니다.

Func<Tree, int> Depth = null; 
Depth = p => p.Parent == null ? 0 : Depth(p.Parent) + 1; 

var depth = tree.Flatten().Select(p => new { ID = p.NodeID(), HowDeep = Depth(p) });