3

いくつかのスプレー ツリーアルゴリズムを実装しました。

それらを比較する最良の方法は何ですか？

ランダムノードを追加したときの実行時間を比較するのは良い出発点ですか?

また、各ノードがどれだけアクセスされたかを追跡する二分探索ツリーも実装しました。optimize()最適二分探索木を作成するメソッドを書きました。
検索ツリーを変更する予定がなく、各アイテムがアクセスされる頻度が正確にわかっている場合は、最適な二分探索ツリーを構築できます。これは、アイテムを検索する平均コスト (期待される検索コスト）を最小限に抑えます。
スプレーツリーの比較にこれをどのように含めることができますか?

4

1 に答える 1

2

私は経験的なアプローチが好きです。

このアプローチでは:

  1. さまざまな長さのランダムな典型的なデータ セットの束を作成します。
  2. 各実装を実行し、それぞれの実行時間を調べます。
  3. 仮説検定法を使用して、ある実装が他の実装よりも優れているかどうかを調べます。ここで、帰無仮説(H 0 ) は、「2 つの実装の実行には、平均して同じ時間がかかるはずです。
  4. ステップ 3 から、1 つの実装が他の実装よりも優れていると1-p結論付けpます。

PS Wilcoxon 検定は優れた検定であると考えられており、2 つのアルゴリズムを比較するために文献や研究で多く使用されています。

于 2013-10-19T15:41:09.683 に答える