大量のデータ (1 億など) から上位 100,000 の最大値を除外するにはどうすればよいですか?

私は大学の 3 年生で、コンピューターを専攻しておらず、Web 開発を独学で学んでいます。数日前、PHP のインターンシップの面接を受けていたとき、面接官がアルゴリズムについて質問しましたが、私はそれに答えられませんでした。最後に質問しようと思っていましたが、結局緊張して質問を忘れてしまいました。Zhihuの専門家がアイデアを提供してくれることを願っています。どの言語でも構いません
====================== ============== =================================
補足：初期不良でメモリやディスクが故障しています。この質問の入り口が分からないので、メモリにあるかディスクにあるかは質問しません。両方の状況について包括的な回答が得られることを願っています。

返信内容:

問題は、N 個の数値の中から最初の k 個の数値を見つけることです。

1 億 = 100M は、現在のハードウェアと比較すると非常に小さい数であり、基本的にはすべてメモリに収まります。メモリ内の上位 k 個の数値を見つけるには、平均複雑度 O(N) のクイックソートに似たアルゴリズムであるクイック選択アルゴリズムを使用できます。

データの総量が大きい場合、または使用可能なメモリが小さい場合は、すべての数値をメモリに配置できる複数の部分に分割し、各部分で上位 k 個の数値を見つけて、最後にすべての数字を一緒に並べます。もう一度上位の K を探して、それでも数字を置くことができない場合は、続けてそれらを山に分割します。この戦略により、アルゴリズムを並列実行することもできるため、コンピューティング リソースが利用可能な場合、全体の実行時間が短縮されます。

このアルゴリズムは、サイズ k の最大ヒープを構築するよりも高速です。これは、後者によって最終的に取得される k 個の数値が部分的に順序付けされており、複雑さが O(N log k) になるのに対し、前者は最初のヒープを取得するためです。 k 数は完全に順序付けされていません。 データ構造について学んだことがありますか? ミニヒープと呼ばれるものがあります。
----------------------------------------------- --- ------------------------
メモリには制限があり、ディスクには 1 億個のデータを配置できます。さらに、最小 100,000 データのヒープを収容するためにメモリ内にスペースを開くことができます。
最小ヒープがいっぱいでない場合は、毎回ディスクから 1 つのデータを読み取り、最小ヒープのプロパティに適合するようにヒープを調整します。 min-heap がいっぱいです。この数値を min-heap と比較します。ルート ノードの値がルート ノードの値より大きい場合、ルート ノードの値が置き換えられ、最小ヒープが計算されます。最小ヒープのプロパティに適合するように再調整されました。
1 億個のデータを走査した後、最初の 100,000 個の最大値が、容量 100,000 のこの最小ヒープに保存されます。 慎重に答えてください。
まず第一に、データ量が 1 億の場合、要件が高くなければ、最初の 100,000 個の最大の数値を維持するために最小限のヒープしか使用できません。
数値の合計数が N で、選択される数値が M であるとします。このとき、この方法によってもたらされる時間計算量は次のようになります。
これ。この方法の最大の欠点は、 並列計算 がないことです。
データ量が 100 億 など、1 億を超える場合は、並列コンピューティングを使用する必要があります。私の考えを詳しく説明します。
1) まず、これらのデータを K 個のヒープにランダムに分割します。それらは均等に分散されており、時間計算量は であると仮定できます。
2) K 個のタスクを使用して、各パイル内の最初の M 個の最大数を並列に選択します。このとき、長さ M の順序付けされたシーケンスの K 個のグループが生成されます。 3) 多方向マージ ソートを使用して、これらの K 個のシーケンス セット内の最大の上位 M 個の数値を選択します。このステップの時間計算量は
したがって、ステップ 2 が並列で完了すると仮定すると、全体的な時間計算量 以上です
。この時点で、アルゴリズムは一定のレベルで最適化されています。 しかし、まだ終わっていません。2) では、各シーケンスに対して上位 M 個の最大の数値が選択されることに注意してください。これは引き続き改善される可能性があります。
シナリオを想像できます。2 つのバケツに合計 10 個のボールがあり、操作ではこれら 2 つのバケツから最大 L 個のボールを取得できると規定されています。許容できる確率ですべてのボールを獲得できるようにするには?
L=10 の場合、もちろんすべてのボールを 100% 獲得できますが、コストが高すぎます。ボールはランダムに配布されるため、10 個のボールがすべて 1 つのボックスに入る確率は非常に小さいことがわかります。つまり、
です。したがって、まずこの種の招待を宝くじ当選イベントとして扱い、当面は無視して、L を直接 9 に設定することができます。 オーバーヘッドを減らすために信頼性をある程度犠牲にしているのに、なぜ L をより低く設定できないのでしょうか?どれくらい低く設定すればいいのでしょうか？
これは実際には別の問題です。この問題を解決するには、L から始める必要はありません。代わりに、許容可能な最低の信頼性確率 P を設定し、要件を満たす最小の L を見つけます。
したがって、上記の方法を使用して 2) を最適化できます。必要な最小信頼性が P で、最適化関数が
であると仮定します。2) K 個のタスクを使用して、各パイルの上位 個の最大数を並列で選択します。このステップの時間計算量は , このとき、長さ の順序付けされたシーケンスのグループが K 個生成されます。 この関数の威力を確認するために、数値
を与えることができます。したがって、この方法を使用すると、実際には何倍もの速度向上を達成できます。 しかし、解決しなければならない問題は信頼性の問題ですが、この問題は実際には 3) で数列が使い尽くされているかどうかを確認するだけで済み、最後の数字がこの中にない場合にのみ解決できます。最後の数字は、このシーケンスの
番目の数字も最悪の結果に現れる可能性があることを意味します。最も簡単な方法は、このシーケンスからデータを追加して、最終的な答えを正しくすることです。 これで、成功率が P のアルゴリズムが得られます。このアルゴリズムは、最適化前よりも何倍も高速になる可能性がありますが、勝利確率は (1-P) です。良いニュースは、勝ったかどうかを判断できることです。そうでない場合は、結果を破棄して、最適化されていないアルゴリズムを再度実行できます。 ヒープソート + 分割統治 m は最初の n
を受け取ります。小さい方を例として考えてみましょう。小さいのが好きです。
データの総量に基づいて、小、中、大の 3 つの状況に分類されます。

1. Small: すべてをメモリに読み込み、並べ替えて、上位 n 個を取得します。

2. 中:
2.1: 複数回読み取り (回数は k = 総データ/メモリ サイズ)、それぞれ読み取りエントリ ポイントをソートして書き戻します。全部読んでみてください。 k 個の連続した文字列 (データ コーンと呼ばれます) を形成します。
2.2: 各コーンは 1 つのセクション (量はメモリ/K) をメモリ (コーンセクションと呼ばれます) に読み取ります。
2.2: 各コーンの先端が比較され、小さい方が別のメモリ領域 (出力バッファーと呼ばれます) に書き込まれます。たとえば、特定のコーンの低速セクションが空の場合は、コーンの次のセクションを読み取ります。
2.3: 出力バッファがいっぱいになります。
2.4: 結果ファイルに書き込みます。
2.5: 結果があれば十分、それで終わりです。それ以外の場合は、2.2 に進みます。

3. 大:
3.1: 複数の単一マシン、2.1 から 2.3 を実行し、一時停止します。
3.2: 配電盤として使用される別のスタンドアロン マシン。各単一マシンの出力バッファ領域から、1 つのセクションを配電盤のメモリ領域 (トータル コーン セクションと呼びます) に読み取ります。
3.3: 各合計コーンの先端を比較し、小さい方が配電盤の別のメモリ領域 (合計出力バッファ領域と呼ばれます) に書き込まれます。たとえば、特定の合計コーン セクションが空の場合、このコーンに対応する単一マシン出力バッファの次のセクションを読み取ります。
3.4: 合計バッファ領域がいっぱいになり、結果ファイルが書き込まれます。
3.5: 結果があれば十分、それで終わりです。それ以外の場合は、3.3 に進みます。

大量のデータが必要な場合。シュンチュアンをするのは必然です。
上記のアルゴリズムは、十分な結果が得られると早期に終了します。
コーンセクションは常に比較的小さいです。したがって、@Jie Chuan の必勝法は必要ないかもしれません。
抽選方法は楽しいですが。 K の最小数は、この考え方と非常に似ています。 私は長い間データ構造に触れていないので、思考フレームワークについてのみ話すことができます。

1. 最初に最初の 100,000 個の数値を調べ、それらを順序付けされたデータ構造に入れ、この数値グループの最小値 B を記録します。

2. 次の 100,000 個の数値を調べます。 1 万の数値を取り出し、それを順序付き構造の最小値 B と比較します。それが最小値 B より大きい場合、A は順序付き配列に入り、最小値 B は順序付き配列から出ます。 >
3. 順序付けされた配列の最小値 B を再計算します。

4. このプロセスを最後まで繰り返します。

----------

1 億個の数値をたどっても時間を短縮することはできないため、プログラムのパフォーマンスは次のとおりです。 100,000 個の数値の中から最小値をできるだけ早く見つける方法。

これはバイナリ ツリーが最も得意とする問題です。バイナリ ツリーをトラバースしながら、バイナリ ツリーの並べ替えと挿入も完了しました。
申し訳ありませんが、二分木の書き方をほとんど忘れてしまいました。 o_o||
最初にトラバースしてから山に分割します。たとえば、0 ～ 999999 が 1 つの山、100000 ～ 199999 が 2 つの山です。

つまり、n 山の範囲は (n-1)*100000 です。 to n*100000-1

分割後、最大の山から十分な数になるまで進めていきます。

たとえば、最初の山の数が 100,000 を超える場合は、続行できます。たとえば、最大の山の数が 110,000 の場合、最小の 10,000 を除外する方法も使用できます。

10W の数値が複数のヒープに分散されている場合は、最初のいくつかのヒープすべて、最後のヒープの一部、および最後のクリティカル ヒープが存在する必要があります。この時点で、ヒープの分割を続けることもできます。双方向ループを使用できます。リンク リストには少量の上位 N が必要です。

もちろん、10W ノードの双方向循環リンク リストを使用して、しっぽ。

時間計算量は

n

log n * m

ここで、n=100000、m は配列の長さ、

数年前、Baidu 複合検索部門が PHP に面接していたとき、太った面接官が上位 N 人の選択について質問しました。答えは、双方向の循環リンク リストを使用することでした。ノードの数は N でした。しかし、当時の状況では、n は非常に小さく、わずか 5 人でした。

バイナリツリーを構築した方が良いのですが、その場でバイナリツリーを書くことができなかったので、バイナリツリーは使用しませんでした。