検索
ホームページバックエンド開発PHPチュートリアル大量のデータ (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 であるとします。このとき、この方法によってもたらされる時間計算量は次のようになります。大量のデータ (1 億など) から上位 100,000 の最大値を除外するにはどうすればよいですか?
これ。この方法の最大の欠点は、 並列計算 がないことです。
データ量が 100 億 など、1 億を超える場合は、並列コンピューティングを使用する必要があります。私の考えを詳しく説明します。
1) まず、これらのデータを K 個のヒープにランダムに分割します。それらは均等に分散されており、時間計算量は O(N) であると仮定できます。
2) K 個のタスクを使用して、各パイル内の最初の M 個の最大数を並列に選択します。このとき、長さ M の順序付けされたシーケンスの K 個のグループが生成されます。 O(frac{N}{K}logM) 3) 多方向マージ ソートを使用して、これらの K 個のシーケンス セット内の最大の上位 M 個の数値を選択します。このステップの時間計算量は
O(MlogK) したがって、ステップ 2 が並列で完了すると仮定すると、全体的な時間計算量 以上です
。この時点で、アルゴリズムは一定のレベルで最適化されています。 大量のデータ (1 億など) から上位 100,000 の最大値を除外するにはどうすればよいですか?しかし、まだ終わっていません。2) では、各シーケンスに対して上位 M 個の最大の数値が選択されることに注意してください。これは引き続き改善される可能性があります。
シナリオを想像できます。2 つのバケツに合計 10 個のボールがあり、操作ではこれら 2 つのバケツから最大 L 個のボールを取得できると規定されています。許容できる確率ですべてのボールを獲得できるようにするには?
L=10 の場合、もちろんすべてのボールを 100% 獲得できますが、コストが高すぎます。ボールはランダムに配布されるため、10 個のボールがすべて 1 つのボックスに入る確率は非常に小さいことがわかります。つまり、
です。したがって、まずこの種の招待を宝くじ当選イベントとして扱い、当面は無視して、L を直接 9 に設定することができます。 frac{1}{2^9} オーバーヘッドを減らすために信頼性をある程度犠牲にしているのに、なぜ L をより低く設定できないのでしょうか?どれくらい低く設定すればいいのでしょうか?
これは実際には別の問題です。この問題を解決するには、L から始める必要はありません。代わりに、許容可能な最低の信頼性確率 P を設定し、要件を満たす最小の L を見つけます。
したがって、上記の方法を使用して 2) を最適化できます。必要な最小信頼性が P で、最適化関数が varphi (K,M,P)
であると仮定します。2) K 個のタスクを使用して、各パイルの上位 varphi (K,M,P) 個の最大数を並列で選択します。このステップの時間計算量は , このとき、長さ O(frac{N}{K} logvarphi (K,M,P)) の順序付けされたシーケンスのグループが K 個生成されます。 varphi (K,M,P)この関数の威力を確認するために、数値
を与えることができます。したがって、この方法を使用すると、実際には何倍もの速度向上を達成できます。 varphi (16,1000,0.999)leq 94しかし、解決しなければならない問題は信頼性の問題ですが、この問題は実際には 3) で数列が使い尽くされているかどうかを確認するだけで済み、最後の数字がこの中にない場合にのみ解決できます。最後の数字は、このシーケンスの
番目の数字も最悪の結果に現れる可能性があることを意味します。最も簡単な方法は、このシーケンスからデータを追加して、最終的な答えを正しくすることです。 varphi (K,M,P)+1これで、成功率が 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 人でした。

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

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
セッションを保存するためにデータベースを使用することの利点は何ですか?セッションを保存するためにデータベースを使用することの利点は何ですか?Apr 24, 2025 am 12:16 AM

データベースストレージセッションを使用することの主な利点には、持続性、スケーラビリティ、セキュリティが含まれます。 1。永続性:サーバーが再起動しても、セッションデータは変更されないままになります。 2。スケーラビリティ:分散システムに適用され、セッションデータが複数のサーバー間で同期されるようにします。 3。セキュリティ:データベースは、機密情報を保護するための暗号化されたストレージを提供します。

PHPでカスタムセッション処理をどのように実装しますか?PHPでカスタムセッション処理をどのように実装しますか?Apr 24, 2025 am 12:16 AM

PHPでのカスタムセッション処理の実装は、SessionHandlerInterfaceインターフェイスを実装することで実行できます。具体的な手順には、次のものが含まれます。1)CussentsessionHandlerなどのSessionHandlerInterfaceを実装するクラスの作成。 2)セッションデータのライフサイクルとストレージ方法を定義するためのインターフェイス(オープン、クローズ、読み取り、書き込み、破壊、GCなど)の書き換え方法。 3)PHPスクリプトでカスタムセッションプロセッサを登録し、セッションを開始します。これにより、データをMySQLやRedisなどのメディアに保存して、パフォーマンス、セキュリティ、スケーラビリティを改善できます。

セッションIDとは何ですか?セッションIDとは何ですか?Apr 24, 2025 am 12:13 AM

SessionIDは、ユーザーセッションのステータスを追跡するためにWebアプリケーションで使用されるメカニズムです。 1.ユーザーとサーバー間の複数のインタラクション中にユーザーのID情報を維持するために使用されるランダムに生成された文字列です。 2。サーバーは、ユーザーの複数のリクエストでこれらの要求を識別および関連付けるのに役立つCookieまたはURLパラメーターを介してクライアントに生成および送信します。 3.生成は通常、ランダムアルゴリズムを使用して、一意性と予測不可能性を確保します。 4.実際の開発では、Redisなどのメモリ内データベースを使用してセッションデータを保存してパフォーマンスとセキュリティを改善できます。

ステートレス環境(APIなど)でセッションをどのように処理しますか?ステートレス環境(APIなど)でセッションをどのように処理しますか?Apr 24, 2025 am 12:12 AM

APIなどのステートレス環境でのセッションの管理は、JWTまたはCookieを使用して達成できます。 1。JWTは、無国籍とスケーラビリティに適していますが、ビッグデータに関してはサイズが大きいです。 2.cookiesはより伝統的で実装が簡単ですが、セキュリティを確保するために慎重に構成する必要があります。

セッションに関連するクロスサイトスクリプティング(XSS)攻撃からどのように保護できますか?セッションに関連するクロスサイトスクリプティング(XSS)攻撃からどのように保護できますか?Apr 23, 2025 am 12:16 AM

セッション関連のXSS攻撃からアプリケーションを保護するには、次の測定が必要です。1。セッションCookieを保護するためにHTTPonlyとセキュアフラグを設定します。 2。すべてのユーザー入力のエクスポートコード。 3.コンテンツセキュリティポリシー(CSP)を実装して、スクリプトソースを制限します。これらのポリシーを通じて、セッション関連のXSS攻撃を効果的に保護し、ユーザーデータを確保できます。

PHPセッションのパフォーマンスを最適化するにはどうすればよいですか?PHPセッションのパフォーマンスを最適化するにはどうすればよいですか?Apr 23, 2025 am 12:13 AM

PHPセッションのパフォーマンスを最適化する方法は次のとおりです。1。遅延セッション開始、2。データベースを使用してセッションを保存します。これらの戦略は、高い並行性環境でのアプリケーションの効率を大幅に改善できます。

session.gc_maxlifetime構成設定とは何ですか?session.gc_maxlifetime構成設定とは何ですか?Apr 23, 2025 am 12:10 AM

thesession.gc_maxlifettinginttinginphpdethinesthelifsessessiondata、setinseconds.1)it'sconfiguredinphp.iniorviaini_set()。 2)AbalanceSneededToAvoidPerformanceIssues andunexpectedLogouts.3)php'sgarbagecollectionisisprobabilistic、影響を受けたBygc_probabi

PHPでセッション名をどのように構成しますか?PHPでセッション名をどのように構成しますか?Apr 23, 2025 am 12:08 AM

PHPでは、session_name()関数を使用してセッション名を構成できます。特定の手順は次のとおりです。1。session_name()関数を使用して、session_name( "my_session")などのセッション名を設定します。 2。セッション名を設定した後、session_start()を呼び出してセッションを開始します。セッション名の構成は、複数のアプリケーション間のセッションデータの競合を回避し、セキュリティを強化することができますが、セッション名の一意性、セキュリティ、長さ、設定タイミングに注意してください。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

SecLists

SecLists

SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。