配列のソートされた値を検索するために、バイナリ検索よりも高速なアルゴリズムはありますか？
私の場合、A配列内にソートされた値（任意のタイプの値である可能性があります）がnあります。探していた値が次の範囲内にある場合は、返す必要があります。A[n] and A[n+1]
32872 次
12 に答える
43
値が整数の場合、O（log n）よりもうまくいく可能性があります。その場合、nに関して達成できる最悪の場合の実行時間は、O（sqrt（log n））です。そうでなければ、入力シーケンスにパターンがない限り、O（log n）を打ち負かす方法はありません。整数の場合、O（log n）を打ち負かすために使用される2つのアプローチがあります。
まず、ハッシュテーブルにそのプレフィックスを持つ少なくとも1つの整数を格納しているすべてのプレフィックスを格納することによって機能するy-fastツリーを使用できます。これにより、バイナリ検索を実行して、最長一致プレフィックスの長さを見つけることができます。これにより、時間O（log w）で検索している要素の後継を見つけることができます。ここで、wはワードのビット数です。これを機能させ、線形空間のみを使用するために機能する詳細がいくつかありますが、それほど悪くはありません（以下のリンクを参照）。
次に、フュージョンツリーを使用できます。これは、ビットトリックを使用して、一定数の命令でw ^ O（1）比較を実行できるようにし、実行時間をO（log n / log w）にします。
これら2つのデータ構造間の最適なトレードオフは、log w = sqrt（log n）の場合に発生し、実行時間はO（sqrt（log n））になります。
上記の詳細については、Erik Demaineのコースの講義12および13を参照してください：http：//courses.csail.mit.edu/6.851/spring07/lec.html
于 2010-10-30T05:23:39.673 に答える
6
1つの可能性は、関数の根を見つけるように扱うことです。基本的に、見つける：
a[i] <= i <= a[i + 1]
と同等です：
a[i] - i <= 0 <= a[i + 1] - i
次に、ニュートン法などを試すことができます。これらの種類のアルゴリズムは、動作するときに二分探索よりも速く収束することがよくありますが、すべての入力に対して収束することが保証されているアルゴリズムはわかりません。
于 2010-10-30T04:53:51.010 に答える
5
はいといいえ。はい、二分検索よりも平均して高速な検索があります。しかし、私はそれらがまだO（lg N）であり、定数が低いと信じています。
要素を見つけるのにかかる時間を最小限に抑えたいと考えています。一般に、使用するステップを少なくすることが望ましく、これにアプローチする1つの方法は、各ステップで削除される要素の予想数を最大化することです。二等分では、常に正確に半分の要素が削除されます。要素の分布について何か知っていれば、これよりもうまくいくことができます。ただし、パーティション要素を選択するためのアルゴリズムは、通常、中間点を選択するよりも複雑であり、この余分な複雑さは、より少ないステップを使用することで得られると予想される時間の節約を圧倒する可能性があります。
実際、このような問題では、検索アルゴリズムよりも、キャッシュの局所性などの2次効果を攻撃する方が適切です。たとえば、二分探索を繰り返す場合、同じ少数の要素（1番目、2番目、および3番目の四分位数）が非常に頻繁に使用されるため、それらを単一のキャッシュ行に配置する方が、リストへのランダムアクセスよりもはるかに優れている可能性があります。
各レベルを（2ではなく）4つまたは8つの等しいセクションに分割し、それらを線形検索することも、二分検索よりも高速である可能性があります。線形検索では、パーティションを計算する必要がなく、データの依存関係が少ないためです。キャッシュストールを引き起こします。
しかし、これらはすべてO（lg N）のままです。
于 2010-10-30T04:46:30.777 に答える
5
リスト内の値が均等に分散されている場合は、バイナリ分割の代わりに加重分割を試すことができます。たとえば、目的の値が現在の下限から現在の値までの3分の1である場合は、次の要素を試すことができます。また、3分の1の方法です。ただし、値がまとめられているリストでは、これはひどく苦しむ可能性があります。
于 2010-10-30T04:46:49.870 に答える
5
次のアルゴはどうですか？これは指数探索と呼ばれ、二分探索のバリエーションの1つです。 http://en.m.wikipedia.org/wiki/Exponential_search
サイズnのソートされた配列Aで要素kを検索します。Aのkの位置を超えるまで、i = 0、1、2、...のA [2 ^ i]を検索します。次に、配列の左側（小さい方）の部分でiよりも小さいバイナリ検索を実行します。
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
このアルゴリズムはO（log idx）で実行されます。ここで、idxはAのkのインデックスです（両方のstpesはlog idxにあります）。最悪の場合、kがAの最大要素の中にあるか、Aのどの要素よりも大きい場合、アルゴリズムはO（log idx）にあります。乗法定数は二分探索の場合よりも大きくなりますが、非常に大きい場合はアルゴリズムの実行速度が速くなります。配列と、配列の先頭に向かっているデータを探す場合。
このアルゴが二分探索よりも好ましい最小サイズnについて考えたいのですが、わかりません。
于 2013-09-04T14:56:45.597 に答える
2
まず、最適化を行う前に測定します。
その検索を本当に最適化する必要がありますか？
もしそうなら、次に、最初にアルゴリズムの複雑さについて考えてください。たとえば、配列の代わりにツリー（たとえば、などstd::map）を使用できますか？もしそうなら、それは挿入/削除と検索の相対的な頻度に依存しますが、ソートされた配列が手元にあるという前提は、データセットの変更と比較して検索が頻繁であることを示しているので、挿入/削除。各検索をはるかに高速にします。つまり、対数時間です。
実際に検索時間がアドレス指定が必要なボトルネックであり、データ表現の変更が不可能であり、リストが短い場合は、比較ごとの作業が少ないため、線形検索は一般的に高速になります。
それ以外の場合、リストが長く、値の特定の分布が不明または想定されておらず、値を数値として扱うことができず、メモリ消費量を一定にする必要がある場合（たとえば、ハッシュテーブルの作成を除外）、バイナリ検索比較ごとに1ビットの情報を生成し、おそらく最初の検索で実行できる最善の方法です。
乾杯＆hth。
于 2010-10-30T06:04:08.007 に答える
1
それらはいつでもハッシュテーブルに入れることができ、検索はO（1）になります。ただし、メモリを大量に消費するため、アイテムを追加し続ける場合は、ハッシュテーブルを再バケット化する必要があります。再バケット化はO（n）ですが、O（1）に償却されます。それは基本的に、そのスペースに余裕があるかどうかと、潜在的なキャッシュミスに依存します。
于 2010-10-30T04:46:48.897 に答える
1
一般的なケースでは、O（log N）よりも優れた結果を出すことはできませんが、少なくともそれを最適化できるため、O（log N）の前の比例定数を大幅に減らすことができます。
同じ配列で複数の検索を実行する必要がある場合は、SIMD拡張命令を使用してこれらをベクトル化できるため、計算コストをさらに削減できます。
特に、特定のプロパティを満たす浮動小数点数の配列を扱っている場合は、O（1）で配列を検索できる特別なインデックスを作成する方法があります。
上記のすべての側面について、次のテスト結果で説明します 。Cannizzo、2015年、浮動小数点数のソートされた配列の幅広いドメインに適用可能なO（1）のバイナリ検索の高速でベクトル化可能な代替案このペーパーには、 github のソースコードが付属しています。
于 2017-05-20T02:24:38.817 に答える
1
その他のコメントで言及されていますが、この特定の質問（「任意の型、配列内の値」）に対する自然で単純な答えは補間検索になると思います。
中点を計算する代わりに、補間検索は、配列の最低要素と最高要素、および配列の長さを考慮して、ターゲット値の位置を推定します。多くの場合、中点が最良の推測ではないことに基づいて機能します。たとえば、ターゲット値が配列の最上位の要素に近い場合、配列の終わり近くにある可能性があります。
引用元：https ：//en.wikipedia.org/wiki/Binary_search_algorithm
メインページ：https ：//en.wikipedia.org/wiki/Interpolation_search
一様分布の仮定の下で、それは近づくことができますO(log log N)
最近のCPUはメモリアクセスに比べて非常に高速であるため（ディスクの場合と同じようにRAMのプログラム）、インデックス/比較の計算は各データフェッチに比べて安価である可能性があります。検索が十分に絞り込まれたら（メモリ/キャッシュの局所性を利用して）、線形検索でもう少しパフォーマンスを上げることも可能かもしれません。
于 2020-11-02T12:23:36.007 に答える
0
バイナリ検索では、リストを2つの「サブリスト」に分割し、値を含む可能性のあるサブリストのみを検索します。アレイの大きさにもよりますが、アレイを3つ以上のスプライスに分割すると、スピードアップが見られます。
インデックスを保持することにより、最初に検索する配列のどの領域を検索する必要があるかを判断できます。大都市の電話帳のように、外から見ることができ、検索を開始する必要があります。（私は自分の考えをテキストで表現するのに苦労していて、それをよりよく説明する英語のリンクをまだ見つけられませんでした）。
于 2010-10-30T04:57:02.723 に答える
0
見つけるべき数が膨大で、いくつかのまぐれによってそれらもソートされている場合は、O（n + m）でそれを行うことができます。ここで、mは見つけるべき数です。基本的には、典型的なマージアルゴリズムですが、チェックされた各数値が配列に挿入された場合に、どの値が前に挿入されるかを記録するためにわずかな変更が加えられています。
あなたはいつでもスペースをトレードオフすることができます...そして他の操作の時間。すべての要素が一定サイズのpビットであると仮定すると、検索できる値ごとに、現在格納されている次に大きい値のインデックスを格納する大規模な配列を作成できます。この配列は2^p * lg（n）ビットである必要があります。ここで、nは格納されている数値です。各挿入または削除はO（2 ^ p）ですが、これらすべてのインデックスを更新する必要があるため、通常は約2 ^ p/nです。
しかし、ルックアップはO（1）になりました！
OK、OK、それは実際には実用的ではありません。ただし、同様の方法で入力をブロックに分割すると、ログの前の定数が減少する可能性があります。おそらく。
于 2010-10-30T13:33:54.383 に答える
0
誰かが言ったように、あなたは補間検索を試すことができます。しかし、通常、内挿検索は単純な線形アプローチで非常に単純/ダムです（これは、配列Aに値が均等に分布している場合はうまく機能しますが、分布が何らかの方法で大きく歪んでいる場合は非常に不十分です）。
配列Aを数学関数（ソートされているため、1対1の関数）と見なし、近似するという考え方です。100個の値を持つ配列Aがあるとします。ここで、A [x] = 2*xです。次に、配列に9を挿入し、それに最も近い値を置き換えます。
二分探索では、A [50] = 100、次にA [25] = 50、次にA [12] = 24、次にA [6] = 12、次にA [3] = 6、次にヒットします。 A [4] = 8、最後にA [5]=10。A [5] = 9に設定すれば、完了です。
線形補間検索では、最初と最後の値A [0]=0およびA[99]= 198を使用して、2つのf（x）= 2*x間の線形関数を計算できます。逆はg（x）= x/2になります。したがって、9を接続し、g [9] = 4.5、9を超えるA [5] = 10、前の値A [4] = 8を確認すると、完了です。ルックアップと比較は2つだけですが、バイナリ検索の場合は7つです。非常に大きな配列を使用すると、ルックアップと比較が大幅に削減される可能性があることがわかります。
さて、現実の世界では、通常、そのような単純な線形範囲の値を持つ配列はありません。それらはどちらかの側に偏り、補間検索を再帰的に複数回実行するか、1回目または2回目の補間後に線形検索または2分検索に切り替える必要があります。
配列Aの値が大きく歪んでいることがわかっている場合（たとえば、100個の値の配列Aがあり、最初の90個の値が1で、最後の10個の値が1から10の範囲である場合）、補間はおそらく間違った道。二分探索は、ほぼ同じ時間、またはそれより速くそこに到達します。
逆関数を近似する他の配列Bを作成して、それを調べたり、統計分析を行って逆関数を近似する数学関数を作成したりすることもできますが、これはこの回答の範囲を超えています。
于 2021-10-13T19:40:00.557 に答える