c# - XobotOS:为什么 C# 二叉树基准测试使用结构？

Question

对 reputed performance gains 感到好奇在 xobotos 中，我检查了二叉树 benchmark code .

binary tree node 的 Java 版本是:

private static class TreeNode
{
    private TreeNode left, right;
    private int item;
}

C# version是:

struct TreeNode
{
  class Next
  {
    public TreeNode left, right;
  }

  private Next next;
  private int item;
}

我想知道在这里使用结构的好处是什么，因为 Next 和 Previous 指针仍然封装在一个类中。

好吧，有一个 - 叶节点是纯值类型，因为它们不需要左右指针。在一半节点是叶子的典型二叉树中，这意味着对象数量减少了 50%。尽管如此，列出的性能提升似乎要大得多。

问题:还有更多吗？

此外，由于我不会想到在 C# 中以这种方式定义树节点(感谢 Xamarin!)还有哪些其他数据结构可以从以非显而易见的方式使用结构中获益？ (尽管这有点离题并且是开放式的。)

Answer 1

我刚遇到这个奇怪的代码并有同样的问题。如果您更改代码以匹配 Java 版本，它的运行速度会稍微慢一些。我相信大多数“struct TreeNode”无论如何都会被装箱和分配，除了底行。但是，每个节点都会导致 2 次分配:盒装 TreeNode 和类 Next。分配节省很快就消失了。 IMO，这不是对 struct 的适当使用。