PHP の大容量データと大量データ処理アルゴリズムの概要_PHP チュートリアル
- WBOYオリジナル
- 2016-07-21 15:29:37669ブラウズ
以下の方法は、大量のデータを処理するための私の方法の概要です。もちろん、これらの方法ですべての問題を完全にカバーできるわけではありませんが、基本的には、これらの方法で遭遇する問題の大部分に対処できます。以下の質問の一部は、基本的に企業の書面による面接の質問から直接得られたものです。この方法が最善ではないかもしれません。もっと良い方法がある場合は、ぜひ私にご相談ください。
1.ブルームフィルター
適用範囲: データディクショナリの実装、データの重み判定、または集合の交差を見つけるために使用できます
基本原理と重要なポイント:
原理としては非常に簡単ですが、ビット配列 + k 独立したハッシュ関数。ハッシュ関数に対応する値のビット配列を1に設定します。検索中にハッシュ関数の対応するビットがすべて1であることが判明した場合、それは存在することを意味します。当然、この処理は検索を保証するものではありません。結果は100%正しいです。同時に、キーワードに対応するビットが他のキーワードに影響を与えるため、挿入されたキーワードの削除はサポートされていません。したがって、簡単な改善は、削除をサポートするためにビット配列の代わりにカウンター配列を使用するブルームフィルターをカウントすることです。
もう 1 つのより重要な問題があります。それは、入力要素の数 n に基づいてビット配列のサイズ m とハッシュ関数の数を決定する方法です。誤り率は、ハッシュ関数の数 k=(ln2)*(m/n) のときに最小になります。エラー率が E 以下の場合、n 個の要素のセットを表すには、m が少なくとも n*lg(1/E) に等しくなければなりません。ただし、ビット配列の少なくとも半分が 0 である必要があるため、m は大きくする必要があります。その場合、m >=nlg(1/E)*lge でなければなりません。これは、nlg(1/E) の約 1.44 倍です (lg は 2 を意味します)底の対数)。
たとえば、誤り率が 0.01 であると仮定すると、m は n の約 13 倍になるはずです。つまりkは8くらいです。
ここでの m と n の単位は異なることに注意してください。m はビットの単位、n は要素数の単位 (正確には、異なる要素の数) です。通常、単一要素の長さは多くのビットになります。したがって、通常はブルーム フィルターを使用するとメモリが節約されます。
拡張:
ブルームフィルターは、セット内の要素をビット配列にマッピングし、k (kはハッシュ関数の数) のマッピングビットを使用して、要素がセット内にあるかどうかを示します。カウンティング ブルーム フィルター (CBF) は、ビット配列内の各ビットをカウンターに拡張し、要素の削除操作をサポートします。スペクトル ブルーム フィルター (SBF) は、コレクション要素の出現数と関連付けます。 SBF は、カウンターの最小値を使用して、要素の出現頻度を近似的に表します。
問題の例: 2 つのファイル A と B があり、それぞれ 50 億の URL が格納されており、メモリ制限は 4G です。ファイル A と B に共通する URL を見つけてください。ファイルが 3 つ、あるいは n 個あった場合はどうなるでしょうか?
この問題に基づいて、4G=2^32 で約 40 億 *8、つまり約 340 億、n=50 億ビットを計算してみましょう。エラー率が 0.01 の場合、約 650 億ビットが必要になります。現在利用可能なのは 340 億ですが、これはエラー率が増加する可能性があります。さらに、これらの URL が 1 対 1 に対応している場合は、IP に変換することができ、より簡単になります。
2.ハッシュ
適用範囲: 素早い検索と削除のための基本的なデータ構造、通常はデータの総量をメモリに入れることができます
基本原則とキーポイント:
ハッシュ関数の選択、文字列、整数用、順列、特定の対応するハッシュ メソッド。
衝突処理。1 つはオープン ハッシュ (ジッパー方式とも呼ばれます)、もう 1 つはクローズド ハッシュ (オープン アドレス方式、オープン アドレス指定とも呼ばれます) です。 (http://www.my400800.cn)
拡張:
d-left ハッシュの d は複数を意味します。まずこの問題を単純化し、2-left ハッシュを見てみましょう。 2 左ハッシュとは、ハッシュ テーブルをそれぞれ T1 と T2 と呼ばれる等しい長さの 2 つの半分に分割し、T1 と T2 にそれぞれハッシュ関数 h1 と h2 を装備することを指します。新しいキーを格納する場合、2 つのハッシュ関数を同時に使用して計算され、2 つのアドレス h1[key] と h2[key] が取得されます。このとき、T1 の h1[key] の位置と T2 の h2[key] の位置を確認し、どちらの位置に格納（衝突）しているキーが多いかを確認し、負荷の少ない場所に新しいキーを格納する必要があります。両側に同じ番号がある場合、たとえば、両方の位置が空であるか、キーが両方に格納されている場合、新しいキーは左側の T1 サブテーブルに格納され、2-left はこれに由来します。キーを探すときは、2 回ハッシュし、同時に 2 つの場所を探す必要があります。
問題の例:
1) 大量のログデータから、特定の日に Baidu へのアクセス数が最も多かった IP を抽出します。
IP の数は最大 2^32 までに制限されているため、ハッシュを使用して IP をメモリに直接保存してから統計を実行することを検討できます。
3.bit-map
適用範囲: データを素早く検索、決定、削除することができます。一般的に、データ範囲は int の 10 倍未満です
基本原理とキーポイント: ビット配列を使用して、 8桁の電話番号など、何らかの要素が存在するかどうか
拡張子: ブルームフィルターはビットマップの拡張子として見ることができます
問題例:
1) ファイルにいくつかの電話番号が含まれていることがわかっています, 各数字は 8 桁で、異なる数字の数を数えます。
8 ビットの最大数は 99 999 999 で、約 99m ビットと約 10m バイトのメモリが必要です。
2) 2 億 5,000 万個の整数の中から反復しない整数の数を見つけます。メモリ容量がこれらの 2 億 5,000 万個の整数を収容するのに十分ではありません。
ビットマップを展開し、2 ビットを使用して数値を表します。0 は出現しないことを意味し、1 は 1 回出現することを意味し、2 は 2 回以上出現することを意味します。または、それを表すために 2 ビットを使用せず、2 つのビットマップを使用してこの 2 ビットマップをシミュレートできます。
4. ヒープ
適用範囲: 大規模なデータの最初の n は大きく、n は比較的小さいため、ヒープはメモリに配置できます
基本原則と重要なポイント: 最大のヒープはn よりも小さい、最小ヒープは n よりも小さい必要があります。最初の n 番目の最小値を見つけるなどの方法では、現在の要素と最大ヒープ内の最大の要素を比較し、それが最大の要素より小さい場合は、最大の要素を置き換える必要があります。このようにして、最終的に得られる n 個の要素が最小の n になります。最初の n が小さく、n のサイズが比較的小さい場合、最初の n 要素すべてを 1 回のスキャンで取得できるため、非常に効率的です。
拡張機能: デュアル ヒープ、最大ヒープと最小ヒープを組み合わせたものを使用して、中央値を維持できます。
問題の例:
1) 100万個の数字の中から最大の100個の数字を見つけます。
最小 100 要素のヒープを使用してください。
5. 二重層バケツ分割 ----実際には、それは本質的に「分割」のテクニックに焦点を当てた[分割して征服する]という考えです!
適用範囲：k番目の最大値、中央値、非反復または繰り返しの数値
基本原則と重要なポイント：要素の範囲が非常に大きいため、直接アドレス指定テーブルは使用できず、範囲は複数の分割を通じて徐々に決定されます, そして最終的には許容範囲内で行います。複数回ズームアウトできます。二重レイヤーは一例にすぎません。
拡張子:
問題の例:
1) 2 億 5,000 万個の整数の中から非反復整数の数を求めます。これらの 2 億 5,000 万個の整数を収容するにはメモリ領域が十分ではありません。
これは鳩の巣原理に少し似ており、整数の数は 2^32 です。つまり、これらの 2^32 の数値を 2^8 の領域に分割できます (たとえば、領域を表すために 1 つのファイルを使用します)。次に、データを分離します。さまざまな領域に移動し、さまざまな領域でビットマップを使用して直接問題を解決します。つまり、十分なディスク容量があれば簡単に解決できます。
2) 中央値を見つけるには 5,000 万 int を使用します。
この例は上記の例よりも明白です。まず、int を 2^16 の領域に分割し、データを読み込んで各領域に該当する数値の数を数えます。統計結果に基づいて中央値がどの領域に該当するかを判断すると同時に知ることができます。この領域の数値がたまたま中央値となることがあります。次に 2 回目のスキャンでは、この領域に該当する数値のみをカウントします。
実際、それが int ではなく int64 である場合、そのような分割を 3 回行った後、許容可能なレベルまで減らすことができます。つまり、まず int64 を 2^24 の領域に分割し、次にその領域内の最大の数値を決定し、次にその領域を 2^20 のサブ領域に分割し、次にそのサブ領域内の最大の数値を決定します。サブエリアの数値は 2^20 のみであるため、統計には直接 addr テーブルを使用できます。
6. データベースインデックス
適用範囲: 大量のデータの追加、削除、変更およびクエリ
基本原則とキーポイント: 追加、削除、変更を処理するデータの設計および実装方法を使用します。大量のデータのクエリ。
拡張機能:
問題の例:
7. 転置インデックス (転置インデックス)
適用範囲: 検索エンジン、キーワードクエリ
基本原則と重要なポイント: なぜ転置インデックスと呼ばれるのか?全文検索の対象となる文書または文書セット内の単語の保管場所のマッピングを保管するために使用される索引付け方法。
英語を例にとると、インデックス付けされるテキストは次のとおりです:
T0 = "それは何ですか"
T1 = "それは何ですか"
T2 = "それはバナナです"
次のようになります。応答 ファイルのインデックス:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": { 0, 1}
取得された条件「what」、「is」、「it」は、集合の共通部分に対応します。
前方インデックスは、各ドキュメントの単語のリストを保存するために開発されました。前方インデックス クエリは、多くの場合、各文書の順序付けされた頻繁な全文クエリと、検証文書内の各単語の検証を満たします。順方向インデックスでは、ドキュメントが中心の位置を占め、各ドキュメントはそれに含まれる一連のインデックス エントリを指します。つまり、ドキュメントはそのドキュメントに含まれる単語を指し、逆インデックスは単語がそのドキュメントを含むドキュメントを指すことを意味します。この逆の関係は簡単にわかります。
拡張子:
問題の例: 文書検索システム、一般的な学術論文のキーワード検索など、特定の単語がどの文書に含まれているかをクエリします。
8. 外部ソート
適用範囲: ビッグデータソート、重複排除
基本原則とキーポイント: 外部ソートのマージ方法、置換選択敗者ツリー原則、最適マージツリー
拡張機能:
問題例:
1) サイズが 1G のファイルがあり、その中の各行はワードであり、ワードのサイズは 16 バイトを超えず、メモリ制限は 1M です。最も頻繁に使用される 100 個の単語を返します。
このデータには明らかな特徴があります。ワードサイズは16バイトですが、メモリはハッシュ化するには十分ではない1mしかないため、ソートに使用できます。メモリは入力バッファとして使用できます。
9.trie ツリー
適用範囲: 大量のデータ、多くの繰り返し、しかし小さなデータ型をメモリに入れることが可能
基本原則と重要なポイント: 実装方法、ノードの子の表現
拡張機能:圧縮の実装。
問題の例: 1) 10 個のファイルがあり、各ファイルは 1G であり、各ファイルのクエリは繰り返される可能性があります。クエリの頻度で並べ替えるように求められます。
2) 1,000 万個の文字列 (一部は同一 (重複)) は、すべての重複を削除し、重複のない文字列を保持する必要があります。どのように設計して実装すればよいでしょうか?
3). 人気のあるクエリを見つける: クエリ文字列の繰り返しは 1,000 万件を超えませんが、繰り返しを除くと 300 万件を超えることはありません。 255バイト。
10. 分散処理mapreduce
適用範囲: 大量のデータですが、小さいデータ型をメモリに入れることができます
基本原則と重要なポイント: 処理、データ分割、結果の削減。
拡張子:
問題の例:
1)。MapReduce の標準的なアプリケーション例は、ドキュメントのセット内の
それぞれの異なる単語の出現をカウントするプロセスです:
void map(String name, String document):
// name: ドキュメント名
// document: ドキュメントの内容
document 内の各単語 w について:
EmitIntermediate(w, 1);
void reduce(String word, Iterator PartialCounts):
// key: 単語
// 値: 集約された部分カウントのリスト
int result = 0;
partialCounts の各 v について:
result += ParseInt(v);
ここで、各ドキュメントは単語に分割され、それぞれword は、単語を結果キーとして使用して、
Map 関数によって最初に「1」の値でカウントされます。フレームワークは、同じキーを持つすべてのペアを
にまとめ、それらを Reduce への同じ呼び出しに送ります。この関数は、その単語の合計出現数を見つけるために、
すべての入力値を合計するだけで済みます。2) 大量のデータが 100 台のコンピューターに分散されており、このデータのバッチの TOP10 を効率的にカウントする方法を見つけます。
3) 合計 N 台のマシンがあり、各マシンには N 個の番号があります。各マシンは最大 O(N) 個の数値を保存し、それらを操作できます。 N^2 数値の中央値を見つけるにはどうすればよいですか?
古典的な問題分析
数千万または数十億のデータ (重複あり)、最も頻繁に出現する上位 N データを数えます。2 つの状況があります: 一度にメモリに読み込むことができます。そして一度に読むことはできません。
利用可能なアイデア: トライツリー + ヒープ、データベースインデックス、個別のサブセット統計、ハッシュ、分散コンピューティング、近似統計、外部ソート
いわゆる一度にメモリに読み込めるかどうかは、実際にはデータを参照する必要があります重複数量を削除した後。重複排除後にデータをメモリに配置できる場合は、マップ、ハッシュマップ、トライなどを使用してデータの辞書を作成し、統計を直接実行できます。もちろん、各データの出現数を更新するときに、最も出現数の多い上位 N 個のデータを維持するためにヒープを使用することもできます。もちろん、これは検索ほど効率的ではありません。完全な統計後の上位 N データ。
データがメモリに収まらない場合。一方では、この状況に適応するために上記の辞書方法を改善できるかどうかを検討できます。これは、辞書をメモリの代わりにハードディスクに保存することです。データベース。
もちろん、もっと良い方法があります。それは分散コンピューティングを使用することです。これは基本的にマップリデュースプロセスです。まず、データ値またはハッシュ後の値に応じて範囲に従ってデータを異なるマシンに分割できます。データ (md5) の場合は、データを分割してメモリに一度に読み込めるようにして、さまざまな数値範囲 (実際にはマップ) を異なるマシンが処理できるようにするのが最善です。結果を取得した後、各マシンは最も多く出現した上位 N 個のデータを取り出し、それを要約してすべてのデータの中で最も多く出現した上位 N 個のデータを選択するだけで済みます。これが実際には削減プロセスです。
実際、データを別のマシンに直接分散して処理したい場合もありますが、正しい解決策は得られません。あるデータが異なるマシンに均等に分散されている一方で、別のデータは 1 つのマシンに完全に収集されており、同時に同じ数のデータが存在する可能性があるためです。たとえば、最も多く出現する上位 100 個のアイテムを見つけたい場合、1,000 万件のデータを 10 台のマシンに分散し、各マシンで最も多く出現する上位 100 個のアイテムを見つけます。マージ後、実際の 100 番目が見つかることは保証できません。 1 つ目は、たとえば、最も多く発生した 100 番目のマシンには 10,000 がある可能性がありますが、10 台のマシンに分割されているため、各マシンには 1,000 台しか存在しないとします。 1001 個あるので、10,000 個のものは除外されます。各マシンに最も多く出現した 1000 個を選択させてマージしたとしても、1001 個の A が大量に集まる可能性があるため、依然としてエラーが発生します。の個体数が発生しました。したがって、データを異なるマシンにランダムに分散することはできません。代わりに、異なるマシンがさまざまな値を処理できるように、ハッシュ値に従って処理するためにデータを異なるマシンにマッピングする必要があります。
外部ソート方法は大量の IO を消費し、あまり効率的ではありません。上記の分散方法はスタンドアロン バージョンでも使用できます。つまり、合計データが値の範囲に従って複数の異なるサブファイルに分割され、1 つずつ処理されます。処理が完了すると、単語とその出現頻度がマージされます。実際、外部の並べ替えマージ プロセスを使用できます。
また、近似計算を考慮することもできます。つまり、自然言語の属性を組み合わせて、実際に最も多く出現する単語のみを辞書として使用して、このスケールをメモリに入れることができます。