ホームページ  >  記事  >  バックエンド開発  >  2 つのファイル a と b があり、それぞれに 50 億の URL が保存され、各 URL が 64 バイトを占有し、メモリ制限が 4G である場合、ファイル a と b に共通する URL を見つけるにはどうすればよいでしょうか。

2 つのファイル a と b があり、それぞれに 50 億の URL が保存され、各 URL が 64 バイトを占有し、メモリ制限が 4G である場合、ファイル a と b に共通する URL を見つけるにはどうすればよいでしょうか。

WBOY
WBOYオリジナル
2016-08-08 09:32:501330ブラウズ

各ファイルのサイズは 5G*64=300G と推定でき、これは 4G よりもはるかに大きくなります。したがって、処理のためにメモリに完全にロードすることは不可能です。分割統治のアプローチを検討してください。
ファイル a を走査し、url ごとに hash(url)%1000 を取得し、取得した値に基づいて url を 1000 個の小さなファイル (a0、a1、...a999 に設定) に保存します。 。 の間で。この方法では、各小さなファイルのサイズは約 300M になります。ファイル b をトラバースし、a と同じ方法を使用して、url を 1000 個の小さなファイル (b0, b1....b999) に保存します。この処理の後、同じである可能性のあるすべての url は、対応する小さなファイル (a0 対 b0、a1 対 b1....a999 対 b999) 内にあり、対応しない小さなファイル ( など) は存在しません。 a0 と b99) は同じです。次に、1000 ペアの小さなファイルから同じ URL を見つけるだけで済みます。 たとえば、
a0 と b0 の場合、a0 をトラバースして、url を hash_map に保存できます。次に、b0 をトラバースします。url が hash_map にある場合、この url は a と b の両方に存在することを意味します。 分割された小さなファイルが不均一で、一部の小さなファイルが大きすぎる場合 (たとえば、
2G より大きい)、これらの大きすぎる小さなファイルを同様の方法で小さなファイルに分割することを検討できます

昨日百度の面接官が今日勉強しましょうと尋ねました

上記では、指定された 2 つのファイル a と b が紹介されており、それぞれ 50 億の URL が保存され、各 URL は 64 バイトを占有し、メモリ制限は 4G です。ファイル a と b の共通 URL を見つけるにはどうすればよいでしょうか。 、関連コンテンツも含めて、PHP チュートリアルに興味のある友人に役立つことを願っています。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。