1

非線形ビン分布のバイナリ検索よりもヒストグラムを計算するためのより効率的なアプローチはありますか?

私は実際には、キー（値）をビン（伝達関数？）に一致させるアルゴリズムのビットにのみ興味があります。つまり、一連の浮動小数点値について、各値の適切なビンインデックスを知りたいだけです。

線形ビン分布の場合、値をビン幅で割ることで O(1) を取得でき、非線形ビンの場合、バイナリ検索で O(logN) を取得できることを知っています。私の現在の実装では、等しくないビン幅でバイナリ検索を使用しています。

効率を改善するという精神で、ハッシュ関数を使用して値を適切なビンにマップし、幅が等しくないビンがある場合に O(1) 時間の複雑さを達成できるかどうかについて興味がありましたか?

4

4 に答える 4

3

いくつかの単純なケースでは、O(1) を取得できます。

値が 0 から 255 までの 8 ビットであるとします。

それらをサイズ 2、2、4、8、16、32、64、128 の 8 つのビンに分割すると、ビンの値の範囲は 0 ～ 1、2 ～ 3、4 ～ 7、8 ～ 15、16 になります。 -31、32-63、64-127、128-255。

バイナリでは、これらの範囲は次のようになります。

0000000x (bin 0)
0000001x
000001xx
00001xxx
0001xxxx
001xxxxx
01xxxxxx
1xxxxxxx (bin 7)

したがって、(O(1) で) 値の最上位ゼロ ビットの数をすばやく数えることができれば、そこからビン番号を取得できます。

この特定のケースでは、ビン番号を含む 256 要素のルックアップ テーブルを事前に計算することができ、値の適切なビンを見つけることは、1 つのテーブル ルックアップだけです。

実際には、ルックアップ テーブルが小さいため、8 ビット値では任意のサイズのビンを使用できます。

2 の累乗のサイズのビンを使用する場合は、このルックアップ テーブルを 16 ビット値にも再利用できます。そして、2 つのルックアップが必要になります。さらに長い値に拡張できます。

于 2013-03-29T16:47:48.477 に答える
2
于 2013-03-29T21:29:05.140 に答える
2

補間検索はあなたの友達です。これは一種の楽観的で予測的なバイナリ検索であり、各ステップで検索スペースを半分に分割するのではなく、入力の分布に関する線形仮定に基づいてビンがどこにあるべきかを推測します。線形の仮定が真の場合は O(1) になりますが、仮定がそうでない場合でも (速度は遅くなりますが) 動作します。その予測が正確である限り、検索は高速です。

于 2013-03-29T21:35:57.733 に答える
1

ハッシュの実装と使用しているデータのタイプによって異なります。より小さいデータ セットの場合、ハッシュのルックアップ オーバーヘッドが平均して大きい場合、二分探索のようなより単純なアルゴリズムが定数ルックアップよりも優れている可能性があります。ハッシュの通常の実装は、リンクされたリストの配列と、リンクされたリストの配列内のインデックスに文字列をマップするハッシュ関数で構成されます。負荷係数と呼ばれるものがあります。これは、ハッシュ マップ内の要素数 / リンク リスト配列の長さです。したがって、ロード ファクターが 1 未満の場合、リンク リストに複数の要素が含まれないため (最良のケース)、最良のケースで一定のルックアップを実現できます。

どちらが優れているかを確認する方法は 1 つしかありません。ハッシュ マップを実装して、自分の目で確かめてください。一定のルックアップに近いものを取得できるはずです:)

于 2013-03-29T16:29:56.363 に答える