万変はその宗の大量のデータの下のアルゴリズムの問題の処理の構想から離れません

本文は万変がその宗の大量のデータの下のアルゴリズムの問題の処理の構想を離れないことを紹介します
万変はその宗の大量のデータの下のアルゴリズムの問題の処理の構想から離れません
本文は当地で比较的にハンサムな男の金天大神のオリジナルから、著作権はすべて、転載を歓迎して、しかしこの著作権の情报を保留して下さい、协力に感谢して、いかなる疑问があって微信を通じて(通って)私の交流を连络することを歓迎します:jintianiloveu大量のデータの下のアルゴリズムの問題
本文の冒頭では,大量のデータ処理下のアルゴリズム問題という重要な問題を導入した.これは就職活動においても、これからの仕事においても必ず直面しなければならない問題です.そこで、私はここで単独でこの一連の問題の縁起を説明します.大量のデータの中で自分を見失うことはありません.
万変不離の宗である以上、すべての問題が元を追って、真に戻っていくつかの共通の特性を持つ問題であることは間違いない.ここではまず,すべての大量データアルゴリズムの問題を列挙し,実際にはtopK問題,**繰返し問題*,並べ替え問題のいくつかにまとめることができる.この3つの大きな問題は、一般的ではありません.あなたが直面できるすべての大きなデータの大量のデータの問題は、この3つの種類を呼ぶことはありません.
先祭大殺器
この3つの問題を正式に記録する前に、私はいくつかの大殺器を祭る必要があります.これらの方法はビッグデータの問題を処理する上で通用します.つまり、これらの方法は最も基本的な方法ですが、私はできるだけ研究しないのは非常に複雑です.
ビットマップほう
一見、この名前は簡単ですが、実際にはそうではありません.この方法の考えはとてもすごいです.このような問題から見ると、もし2億5000万intの整数があれば、整数をあげて、この整数がこの2億5000万個の整数の中にあるかどうかを判断させましょう.スピードをできるだけ速く要求すると、あなたはどうしますか?多くの人は、私は非常に機知に富んでこれらの整数を遍歴して、同じものがなければ存在しません.もしあれば存在します.そう、これは間違っていませんが、もしまた整数が来たら、中にいるかどうかを判断させます.この時、あなたはもう一度遍歴しなければなりません.これは非常に非科学的なやり方だ.この時、私たちのビットマップ法は牛に迫って現れた.ビットマップ法は,このような問題が存在するか否かを判断するのに適しており,要素の状態が比較的少なく,要素の個数が比較的多い場合である.では、具体的にはどうすればいいのでしょうか.そうすれば、2億5000万個の整数の中で、私は最大整数に等しい文字列を維持しています.各整数が存在するかどうか、私はこの整数に対応する位置を1にしています.例えば、{2,4,5,6,67,5}といういくつかの整数があります.私は00を維持しています.0000 67ビットの文字列.しかし、整数の最大値を知らない場合は、少なくとも1つの長さ232の文字列が必要です.整数の最大値は232です(intは4バイトを占めているので32ビットです).これは少なくとも512 Mメモリで、charの長さからメモリを計算すると、直接*8/2^20はMの単位になります.そう言えばビットマップ法が理解できます.
topK問題
まずtop k問題について検討してみましょう.殺器はすでに送られています.次に、いくつかの古典的なビッグデータの問題を記録します.

には1000万個の身分証明書番号と対応するデータがあり、身分証明書番号が重複し、最も出現回数の多い身分証明書番号を見つけることができます.

には1000000個のレコードがあり、これらのクエリ列の繰返し度は比較的高く、繰返しを除いた場合、300000個を超えない.1つのクエリー・列の重複度が高いほど、クエリーのユーザーが多いこと、つまり人気があることを示します.最も人気のある10個のクエリー列を統計してください.使用するメモリは1 GBを超えてはいけません.

には10個のファイルがあり、各ファイル1 GB、各ファイルの各行にはユーザーのqueryが格納され、各ファイルのqueryは重複する可能性があります.queryの頻度でソートします.

には1 GBサイズのファイルがあり、中の各行は1語で、語のサイズは16バイトを超えず、メモリ制限サイズは1 MBです.最も頻度の高い100語を返します.

は、ある日サイトにアクセスした回数が最も多いIPを抽出する.

の10億個の整数は、繰り返し回数が最も多い100個の整数を見つけた.

が検索した入力情報は文字列で、300万件の入力情報の中で最も人気のある上位10件を統計し、入力するたびに255 Bを超えず、メモリ使用は1 GBしかない.

これらの問題をどう解くか、一緒にゆっくり考えてみましょう.まずここに置いておきましょう.
問題を繰り返す
重複問題には、重複要素を探したり、共通の重複要素を探したりすることが含まれています.同様に、ここでもまず問題をまとめます.

は、例えば、あるファイルにいくつかの電話番号が含まれていることが知られており、各番号は8ビットの数字であり、異なる番号の個数を統計している.

の10億個の正の整数は,1個の数だけ繰り返し出現し,O(n)の時間でこの数を見つけることを要求した.

はa,bの2つのファイルを与え,それぞれ50億個のurlを格納し,各urlはそれぞれ64 Bを占有し,O(n)の時間にa,bファイルの共通のurlを見つけることを要求した.

は40億個の重複しないunsigned intの整数を与えて、順序を並べていないで、それからもう1つの数をあげて、どのように迅速にこの数がその40億個の数の中にあるかどうかを判断しますか?

これらの問題の中で、最も簡単で最も重要なのは問題を重くすることで、私はご飯を食べてから書き続けます.例えば、wifiのパスワード辞書をあげると、重複するパスワードが大幅に増加して無駄になります.削除しなければなりませんが、辞書が少ないと万以上になり、千億以上になります.非常に大きなデータです.どうやって重くしますか.やっとご飯を食べ終わったので、続けましょう.さっき、非常に実行可能な方法を見ました.

             ，    ，      hash  ，              0-n（            ），           500    ，                 ，                ，     ，    sort foo1.txt|unique ，                          。（                       ？）

総じて言えば、大量のデータの重複問題を解決することは、2つの大きな宝物にほかならない.

分治法、hashから小文書まで、ゼロにし、それぞれ破壊する.

ビットマップ法、これは整数の場合にしか適していないようですか?例えば電話番号とか、身分証明書番号とか?

BloomFilterアルゴリズムここでは一つ一つ紹介しませんが、このアルゴリズムは比較的ハイエンドです.

それは最後に、比較的実行可能なのはやはり分けて治療したほうが頼りになるようだ.
ソートの問題
最後に、大量のデータのソートの問題です.これはいちいち言いません...次のブログでは、実際に実戦して、これらの方法で実際のビッグデータの問題を処理します.