>  기사  >  백엔드 개발  >  두 개의 파일 a와 b가 각각 50억 개의 URL을 저장하고 있고 각 URL이 64바이트를 차지하고 메모리 제한이 4G인 경우 파일 a와 b의 공통 URL을 찾는 방법은 무엇입니까?

두 개의 파일 a와 b가 각각 50억 개의 URL을 저장하고 있고 각 URL이 64바이트를 차지하고 메모리 제한이 4G인 경우 파일 a와 b의 공통 URL을 찾는 방법은 무엇입니까?

WBOY
WBOY원래의
2016-08-08 09:32:501313검색

각 파일의 크기는 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)에 있습니다. vs b99) 동일한 URL을 가질 수 없습니다. 그런 다음 1000쌍의 작은 파일에서 동일한 URL을 찾으면 됩니다. 예를 들어
a0과 b0의 경우 a0을 순회하고 url을 hash_map에 저장할 수 있습니다. 그런 다음 b0을 탐색합니다. url이 hash_map에 있으면 이 url이 a와 b에 모두 존재한다는 의미입니다. 분할된 작은 파일이 균일하지 않고 일부 작은 파일이 너무 큰 경우(예:
2G보다 큰 경우), 너무 큰 작은 파일을 비슷한 방식으로 작은 파일로 분할하는 것을 고려해 볼 수 있습니다

어제 바이두 면접관이 오늘 공부하자고 하더군요

위는 주어진 두 파일 a와 b를 소개합니다. 각각은 50억 개의 URL을 저장하고 각 URL은 64바이트를 차지하며 메모리 제한은 4G입니다. 파일 a와 b의 공통 URL을 찾는 방법은 무엇입니까? , 관련 내용을 포함하여 PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.