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

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

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

昨日、百度の面接官から今日勉強するように言われました

1F

ランニングマン

アイデアは良いですが、詳細は少し面倒です