整数の2つの検索ツリー（AVLツリーとRedBlackツリー）のパフォーマンスを比較したいと思います。では、これを達成するためにテストをどのように設計/エンジニアリングする必要がありますか？たとえば、の挿入オペレーションを考えてみましょう。平均してこの操作がRBケースで高速であることを示すにはどのような手順を実行する必要がありますか？ 1つの要素だけを挿入するのに時間を置くべきですか（ツリーがあらかじめ設定されていると仮定して）、または挿入シーケンスを実行する必要がありますか？また、CPU時間を正確に測定するためにはどのような考慮事項が必要ですか？2つのデータ構造の操作の実行時間を比較する方法
ありがとうございます。
これは本当に広い質問です。だから、誰かがここに乗ってパフォーマンスを測定する方法についての最終的な正解を与えることを期待してはいけないと思います。それは言われている...
まず、一連のテストを開発する必要があります。アプリケーションで実際に行われている操作のシーケンスを監視する（つまり、AVLまたはRBツリーのいずれかを使用するオープンソースアプリケーションを見つけ、それが実行する操作のシーケンスを出力するコードを追加する）任意の数のケース（平均使用、特定の種類の異常または異常な使用、ランダムな使用など）を対象とする分析的または合成的な操作ストリームを作成することができます。これらの種類のトレースのうち、より多くのものがテストされるほど良いでしょう。
テストするトレースのセットを取得したら、評価を行うドライバを開発する必要があります。ドライバは単純で、AVLとRBツリーの両方で同じでなければなりません（この場合、これは問題ではないはずです;両方ともユーザーと同じインターフェイスを提示しますが、内部実装の詳細に関してのみ異なります）。ドライバは、トレースセットに記録された使用状況を効率的に再現し、トレースされた操作をデータ構造上で実行できるようにする必要があります。私がしたいことの1つは、何もしない第3の「ダミー」候補を含めることです。このようにして、トレースの処理が全体的なパフォーマンスに及ぼす影響の大きさを知ることができます。
各トレースは何度も何度も実行する必要があります。これを幾分公式化することで（既知の範囲内の統計的不確定性を減らすことができます）、経験則は1/sqrt（n）に従って誤差の順序が縮小されることです。ここでnは試行回数です。言い換えると、各トレースを100回ではなく10,000回実行することにより、平均で10倍小さいエラーが発生します。すべての値を記録する。検索するものは、平均値、中央値、モードなどです。実行ごとに、システム条件を同じに保つようにしてください。他のプログラムは実行されていません。外的要因の変化による誤った結果を排除するために、外れ値の下限と上位10％を切り捨てることができます...
ここで単純にデータセットを比較します。あなたが最も気にしているのは、トレースにかかる平均時間です。おそらく最悪？あなたが本当に気にしているのは、一貫性です。大小の標準偏差ですか？両方のテスト構造で実行された特定のトレースの結果を比較するのに十分なデータが必要です。別のトレースでは、異なる数字を見る方が意味があるかもしれません（たとえば、RBツリーの最悪の場合の合成ベンチマークを作成した場合、RBツリーとAVLツリーがどれほど悪いかを尋ねるかもしれませんが、 AVLツリーのベストケースを表す別のトレースなどのためにこれを気にしてください。）
CPUのタイミングは、それ自体が難題です。タイマーの解像度がイベントを測定するのに十分であることを確認する必要があります。 clock（）およびgettimeofday（）関数などは、イベントの時刻を記録するための一般的な選択肢です。トレースが速すぎる場合は、いくつかのトライアルの合計時間を得ることができます（タイマーがマイクロ秒のタイミングをサポートし、トレースが10マイクロ秒で終了する場合は、トレースの実行回数を1回で100回測定し、ミリ秒の10秒。これは正確である必要があります）。
別の潜在的な落とし穴は、毎回同じ実行環境を提供しています。トレース実行の間では、少なくとも、きれいなキャッシュから開始するためのテクニックを検討することができます。そのどちらか、または最初の実行を時間切れにするか、またはアウトライアを排除するときにこの結果が抽出される可能性があることを理解してください。コードAはコードBが犠牲になるかもしれないが、キャッシュの中にはいくつかの値を持つことが恩恵を受けるかもしれないので、（例えば、トレースの実行の間に、ある大きな配列のすべての要素を操作することによって）キャッシュをリセットするほうが安全かもしれません。
これは、独自のパフォーマンス評価を行う際に考慮する可能性があるいくつかの点です。例えば、PAPIや他のプロファイラのような他のツールはヒット/ミス、命令などの特定のイベントを測定することができ、この情報はウォールクロックランタイムの単純な比較よりはるかに優れた比較を可能にします。
CPU時間を正確に測定することは、特定のプログラミング言語、実装などによっては非常に難しい場合があります。たとえば、JavaのJITコンパイルでは、今までにコードをどれだけ実行したかによって結果が大きく異なることがあります。
あなたの状況について詳細を教えてもらえますか？
この広範な答えをありがとう。あなたはキャッシュ部分に関するより多くの情報を持つリンクを提供できますか？つまり、任意のコードがキャッシュにどのような影響を及ぼし、どのようにしてキャッシュを効果的に使用するのかということです。ありがとう。 – jplot