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

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

ということは、各ファイルのサイズは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 より大きい)、これらの大きすぎる小さなファイルを同様の方法で小さなファイルに分割することを検討できます

昨日、百度の面接官がこの質問をしました