C# 如何有效地池化节点树的对象？

Question

我有一个节点 class，它只包含值类型属性和一个引用类型：它是父节点。在执行树搜索时，这些节点会在很短的时间内创建和销毁数十万次。

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 的 Mono 运行时中完成的，所以我想尝试合并节点对象。但是，我不知道如何知道节点对象何时可以安全地 return 到池中，因为仍在使用的其他节点可能会将其作为父节点引用。在搜索结束时，最好的节点被 returned 并通过回溯其祖先形成一个节点列表。如果有用的话，我可以完全控制节点在树中的创建方式。

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

Answer 1

如果您的节点是结构体，请尝试使用 ref 关键字，这样可以避免每次将节点传递给函数时都复制该节点。

因此：

struct Node
{
      object obj;
      Node children;
}

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

Answer 2

所以，幸运的是，如果您正在做一个 Depth-First-Search，这看起来会更容易一些。任何时候到达叶节点，都有两种可能性：该叶节点是当前最深树的一部分，或者不是。

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

现在，如果我们不是叶节点，在我们检查完 children 之前，我们不知道是否可以释放。然后，一旦检查了我们所有的 children，我们就会发现我们的 children 中是否有任何人说他们是当前最好的。如果是这样，我们保持自我

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

这是一些 sudo 代码：

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

C# 如何有效地池化节点树的对象？

C# How to pool the objects of a node tree efficiently?

c#

reference

mono

dispose

pool