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; 
} 

因为这是有一个非常古老的GC单声道运行时完成，我想尝试，集中节点的对象。然而，我不知道如何知道节点对象何时可以安全地返回到池中，因为其他正在使用的节点可能会将其引用为父节点。在搜索结束时，返回最佳节点，并通过回溯其祖先来形成节点列表。如果这很有用，我完全可以控制如何在树内创建节点。

我可以尝试和实施哪些选项？

Answer 1

所以，幸运的是，如果你正在做一个深度优先搜索，你似乎是，这是一个更容易一些。每当你到达一个叶节点时，有两种可能性：叶节点是当前最深的树的一部分，或者它不是。

如果不是，那意味着将此节点返回到池是安全的。如果是这样，那意味着我们可以将旧树中的任何节点返回到我们的池中，这些节点不在我们自己的祖先链中。

现在，如果我们不是一个leafnode，我们不知道我们是否可以在我们完成检查我们的孩子后才能被释放。那么，一旦我们所有的孩子都被检查过，我们就会发现我们的孩子是否说他们是最好的。如果是这样，我们保持自己

这确实意味着我们正在做更多的检查。

下面是一些须藤代码：

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...}