私は最近、「10 億の数字の配列から 100 個の最大の数字を見つけるプログラムを作成してください」という面接を受けました。
私が提供できたのは、配列を O(nlogn) の時間計算量でソートし、最後の 100 個の数字を取得するという、力ずくの解決策だけでした。
Arrays.sort(array);
面接官はより優れた時間計算量を求めていましたが、私は他の解決策をいくつか試しましたが、答えられませんでした。より優れた時間計算量の解決策はあるのでしょうか?
ベストアンサー1
100 個の最大の数字の優先キューを保持し、10 億個の数字を反復処理することができます。キュー内の最小の数字 (キューの先頭) よりも大きい数字に遭遇するたびに、キューの先頭を削除し、新しい数字をキューに追加します。
優先度キューは、山積み挿入 + 削除の複雑さは ですO(log K)。(ここで、K = 100、検索する要素の数。N = 10億、配列内の合計要素数)。
最悪の場合、O(N log N)の比較ベースのソート1よりも優れた結果が得られます。billion*log2(100)billion*log2(billion)
一般に、N 個の数値のセットから最大の K 個の数値が必要な場合、複雑度はO(N log K)ではなく になりますO(N log N)。これは、K が N に比べて非常に小さい場合に非常に重要になる可能性があります。
この優先キュー アルゴリズムの予想時間は非常に興味深いものです。これは、各反復で挿入が発生する場合と発生しない場合があるからです。
i番目の数字がキューに挿入される確率は、ランダム変数が同じ分布からの少なくともランダム変数よりも大きい確率ですi-K（最初のk個の数字は自動的にキューに追加されます）。順序統計を使用できます（リンク）を使用してこの確率を計算します。
たとえば、数字がから一様に{0, 1}ランダムに選択されたと仮定すると、(iK)番目(i個の数字のうち)の数字の期待値は であり(i-k)/i、ランダム変数がこの値よりも大きくなる確率は です1-[(i-k)/i] = k/i。
したがって、挿入の予想される数は次のようになります。
予想される実行時間は次のように表すことができます。
（最初の要素kを含むキューを生成する時間、次に比較、そして上記のように予想される挿入数、それぞれ平均時間がかかります）kn-klog(k)/2
Nが に比べて非常に大きい場合、この式はではなく にKかなり近くなることに注意してください。これは、質問の場合のように、ある程度直感的ですが、10,000 回の反復後でも (10 億に比べると非常に小さい)、数字がキューに挿入される可能性は非常に小さいです。nN log K
しかし、配列の値が均一に分布しているかどうかはわかりません。配列の値は増加する傾向にある可能性があり、その場合、ほとんどまたはすべての数値が、検出された最大 100 個の数値のセットの新しい候補になります。このアルゴリズムの最悪のケースは ですO(N log K)。
あるいは、減少傾向にある場合、上位 100 個の数値のほとんどは非常に早い段階で現れ、最良の実行時間は基本的に となりO(N + K log K)、これは よりもO(N)はるかにK小さくなりますN。
脚注1: O(N) 整数ソート/ヒストグラム
カウンティング ソートや基数ソートはどちらも O(N) ですが、定数係数が大きいことが多く、実際には比較ソートよりもパフォーマンスが低下します。特殊なケースでは、主に狭い整数型の場合、実際にはかなり高速です。
例えば、カウントソート数値が小さい場合はうまく機能します。16 ビットの数値には、2^16 個のカウンターの配列のみが必要です。また、実際にソートされた配列に拡張する代わりに、Counting Sort の一部として構築したヒストグラムをスキャンするだけで済みます。
配列をヒストグラム化すると、任意の順序統計 (たとえば、最大 99 の数値、200 から 100 番目に大きい数値) のクエリにすばやく回答できます。32 ビットの数値では、カウントがはるかに大きなカウンターの配列またはハッシュ テーブルに分散されるため、16 GiB のメモリ (2^32 カウンターごとに 4 バイト) が必要になる可能性があります。また、実際の CPU では、L2 キャッシュが通常ヒットする 2^16 要素の配列とは異なり、TLB ミスやキャッシュ ミスが多数発生する可能性があります。
同様に、基数ソートでは、最初のパスの後に上位のバケットのみを調べることができます。ただし、定数因子はlog K、K に応じて、よりも大きくなる可能性があります。
各カウンターのサイズは、N 個の整数がすべて重複していてもオーバーフローしないほど十分に大きいことに注意してください。10 億は 2^30 より少し小さいので、30 ビットの符号なしカウンターで十分です。また、32 ビットの符号付きまたは符号なし整数でも十分です。
もっと多くのカウンタがある場合は、64 ビット カウンタが必要になる可能性があります。この場合、ゼロに初期化してランダムにアクセスするために、メモリ フットプリントが 2 倍になります。または、16 ビットまたは 32 ビットの整数をオーバーフローする少数のカウンタにセンチネル値を設定し、残りのカウントが他の場所 (64 ビット カウンタにマッピングされるハッシュ テーブルなどの小さな辞書内) にあることを示します。