Каков наилучший способ получить уровень из древовидной структуры данных с помощью LINQ?

Question

У меня есть коллекция, демонстрирующая древовидную структуру данных, это узел:

Node:
Id
Name
ParentID

Теперь я хочу получить 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

С этим классом узла вы можете сделать это легко.

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

Вы можете сделать это сверху вниз n шагами с помощью Breadth First Traversal. Твой подход n*log(n) насколько я вижу?

Быстрый взлом в LinqPad с классом узла с 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();
}

Выходы:

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

Но все зависит от сложности деталей Linq (.Где)

Answer 3

Ниже приведена более компактная версия того, что вы делаете, обратите внимание, что я использовал упрощенную структуру данных для своего теста, и Flatten возвращает IEnumerable каждого узла в дереве из дерева переменных вниз.Я бы сделал функцию рекурсивной глубины частью класса дерева, если у вас есть доступ к этому источнику.Если вы делаете это часто или ваши деревья огромны (или и то, и другое), я особенно согласен с решением кэширования глубины в словаре или самой древовидной структуры.Если вы не делаете это часто, это будет работать нормально.Я использую его для прохождения относительно небольших древовидных структур из графического интерфейса, и никто никогда не думал, что операция была медленной.Сложность - это 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) });

Answer 4

Поскольку вы говорите, что вам нужно получить уровень для каждого узла в этой коллекции, вы можете также создать карту от узла к уровню с нетерпением .

Это можно сделать за 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 5

Попробуйте использовать .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 6

Прямо сейчас вы обрабатываете множество вещей несколько раз.Я бы рекурсивно строил уровни.Таким образом, у вас не будет никаких накладных расходов на обработку.

Кроме того, если вы часто запускаете эту функцию, я бы поместил уровень в классе узла в качестве переменной, которая автоматически вычисляется при добавлении узла.

Исходный код следует.