C# Как эффективно объединить объекты дерева узлов?

Question

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

public class Node 
{ 
    public Node Parent { get; set; } 
    public int A { get; set; } 
    public int B { get; set; } 
    public int C { get; set; } 
    public int D { get; set; } 
} 

Дерево поиска выглядит примерно так:

public static Node GetDepthFirstBest(this ITree tree, Node root) 
{ 
    Node bestNode = root; 
    float bestScore = tree.Evaluate(root); 

    var stack = new Stack<Node>(); 
    stack.Push(root); 

    while(stack.Count > 0) 
    { 
     var current = stack.Pop(); 

     float score = tree.Evaluate(current); 
     if (score > bestScore) 
     { 
     bestNode = current; 
     bestScore = score; 
     } 

     var children = tree.GetChildren(current); 
     foreach(var c in children) { stack.Push(c); } 
    } 

    return bestNode; 
} 

Поскольку это делается в режиме исполнения Mono, который имеет очень старый GC, я хотел, чтобы попытаться объединить объекты узла. Однако я не понимаю, как узнать, когда объект узла безопасен для возврата в пул, поскольку другие узлы, которые все еще используются, могут ссылаться на него как на родителя. В конце поиска возвращается лучший узел, и список узлов формируется путем перехода назад через своих предков. Я полностью контролирую, как узлы создаются внутри дерева, если это полезно.

Какие варианты я мог бы попробовать и реализовать?

Answer 1

Так, к счастью, если вы делаете Depth-First-Search, который вы появляетесь быть, это немного легче. Каждый раз, когда вы достигаете листового узла, есть две возможности: этот листовой узел является частью текущего самого глубокого дерева, или это не так.

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

Теперь, если мы не являемся листовым знаком, мы не знаем, можем ли мы быть освобождены, пока мы не закончим проверку наших детей. то, как только все наши дети будут проверены, мы узнаем, сказал ли кто-нибудь из наших детей, что они в настоящее время лучше всего. если это так, мы держим себя

Это означает, что мы делаем еще немного проверки.

Вот некоторые Судо код:

List bestNodes; 

bool evalNode(node, score) 
{ 
    if (childCount == 0) 
    { 
     if (score > bestScore) 
     { 
      bestScore = score; 
      bestNode = node; 
      bestNodes.Add(node); 

      return true; 
     } 
     else 
     { 
      freeNode(this); 

      return false; 
     } 
    } 
    else 
    { 
     bool inLongest = false; 
     foreach (child in children) 
     { 
      inLongest = evalNode(child, score + 1) || inLongest; 
     } 

     if (!inLongest) 
     { 
      freeNode(node); 
     } 
     else 
     { 
      free(bestNodes[score]); 
      bestNodes[score] = node; 
     }    

     return inLongest; 
    } 
} 

Answer 2

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

Таким образом:

struct Node 
{ 
     object obj; 
     Node children; 
} 

public void DoStuffWithNode(ref Node pNode){...Logic...}