11

xobotosで評判の高いパフォーマンスの向上に興味があったので、バイナリツリーベンチマークコードを確認しました。

バイナリツリーノードのJavaバージョンは次のとおりです。

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

C＃バージョンは次のとおりです。

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

  private Next next;
  private int item;
}

NextポインタとPreviousポインタはまだクラスにカプセル化されているので、ここで構造体を使用する利点は何でしょうか。

1つあります。リーフノードは、左右のポインタを必要としないため、純粋な値型です。ノードの半分が葉である典型的な二分木では、それはオブジェクトの数が50％減少することを意味します。それでも、リストされているパフォーマンスの向上ははるかに大きいようです。

質問：これにはもっとありますか？

また、C＃でこのようにツリーノードを定義することを考えていなかったので（Xamarinに感謝します！）、他のどのデータ構造が非自明な方法で構造体を使用することで利益を得ることができますか？（それは少し話題から外れていて、オープンエンドですが。）

4

4 に答える 4

1

私はこの奇妙なコードに出くわし、同じ質問をしました。Javaのバージョンに一致するようにコードを変更すると、実行速度が少し遅くなります。一番下の行を除いて、「structTreeNode」のほとんどはとにかくボックス化されて割り当てられると思います。ただし、各ノードには、ボックス化されたTreeNodeとクラスNextの2つの割り当てがあります。割り当ての節約はすぐに消えます。IMO、これは構造体の適切な使用法ではありません。

于 2012-12-10T19:23:27.577 に答える
0

構造体はヒープの代わりにスタックに割り当てることができます（ただし、すべての場合ではありません）。つまり、構造体がスコープから外れるとすぐに割り当てが解除されます。ガベージコレクターはそのシナリオに関与しません。これにより、メモリの負荷が少なくなり、ガベージコレクションが少なくなる可能性があります。また、スタックは（ほとんど）メモリの隣接領域であるため、スタックへのアクセスの局所性が向上し、CPUレベルでのキャッシュヒット率を（おそらく）向上させることができます。

クラスと構造のどちらを選択するかに関するMicrosoftのガイドライン：

  • 構造は小さく（一般に16バイト）、短命である必要があります
  • それらは不変でなければなりません

これらが満たされている場合、クラスに対して構造を使用すると、パフォーマンスが向上します。

于 2012-05-17T11:27:35.223 に答える
0

これにより、2つのノードが1つの割り当てにグループ化され、理想的には合計割り当て数が半分になります。

IMOこれにより、比較はかなり無意味になります。

于 2012-05-17T12:16:47.307 に答える
-1

ここで構造体を使用しても、まったく違いはないと思います。特にTreeNodeのソースコードを見た後、TreeNodeのインスタンスは常にコンストラクターと再帰的なbottomUpTree呼び出しでコピーされます。

于 2012-05-17T07:27:21.833 に答える