c++ - フロートをどのビンに入れるかを決定する方法は? C++

Question

Float_t xbins[41]40 個のビン、つまりフロートの範囲を定義するフロートの配列があります。たとえばy、 の場合はビン 7 にありますy > xbins[7] && !(y > xbins[8])。

40 個の if ステートメントを使用せずに、特定のフロートが属するビンを特定するにはどうすればよいですか?

私は他の言語を話せないので、C++ で答えてください。

Answer 1

配列がソートされている場合は、バイナリ検索を実行して正しいビンを見つけます。の組み合わせstd::sort(ソートされていない場合)が必要std::lower_boundです。operator<がに対して正しく実装されていることを確認する必要がありますFloat_t。

Answer 2

ビンの間隔は均一ではなく、整数の境界があることが判明したため、おそらく最速の方法は、明らかに約 100 のエントリを持つ (逆) ルックアップ テーブルを使用することです。基本的に、下限と上限の 2 つの比較を行う必要があります。

配列の境界が数式で導出される場合、LUT メソッドよりも優れた逆数式を記述できる可能性があります。

一般的なケースでは、二分探索がその方法です。それでも、範囲を正確に半分に分割する代わりに、線形補間を行うことで少し改善できます。速度 (データが異常でない場合) は、二分探索の O(logn) と比較して O(loglogn) になります。