두 개의 파일 a와 b가 있고 각각 x와 y 행의 데이터가 있다고 가정합니다. 여기서 (x, y는 모두 10억보다 큼) 머신 메모리 제한은 100M입니다. 같은 레코드가 무엇인지 알아보세요.
이 문제를 처리할 때 가장 어려운 점은 이 대용량 데이터를 한 번에 메모리로 읽어들이는 것이 불가능하다는 것입니다.
읽을 수 없는 경우 한 번에 기억에 남는다면 여러 번 모직물로 간주할 수 있나요? 가능하다면 여러 번 읽어도 동일한 값을 어떻게 계산할 수 있습니까?
우리는 분할 정복 사고를 사용하여 큰 것을 작은 것으로 줄일 수 있습니다. 해싱 후 동일한 문자열의 값이 동일하면 해시 모듈로를 사용하여 레코드를 n개의 파일로 분산시키는 것을 고려할 수 있습니다. 이 n을 얻는 방법? PHP에는 1억 개의 메모리가 있고 배열은 약 1백만 개의 데이터를 저장할 수 있습니다. 따라서 레코드 a와 b에 10억 개의 행만 있다는 점을 고려하면 n은 최소한 200보다 커야 합니다.
현재 200개의 파일이 동일 파일에 있어야 하며, 각 파일을 메모리로 읽어올 수 있습니다. 그러면 이 200개의 파일에서 동일한 레코드를 차례로 찾은 다음 동일한 파일로 출력할 수 있습니다. 최종 결과는 두 파일 a와 b에서 동일한 레코드입니다.
작은 파일에서 동일한 레코드를 찾는 것은 쉽습니다. 레코드의 각 행을 해시 테이블의 키로 사용하고 키의 발생 횟수를 2 이상으로 계산하면 됩니다.
10억 개의 파일이 너무 큽니다. 실용적인 작업은 시간 낭비입니다.
문제 크기는 다음과 같이 줄어듭니다. 메모리 제한은 1M이며, a와 b는 각각 100,000행의 레코드를 갖습니다. 메모리 제한은 PHP의 ini_set('memory_limit', '1M');로 제한할 수 있습니다. ini_set('memory_limit', '1M');来限制。
生成随机数用于填充文件:
/**
* 生成随机数填充文件
* Author: ClassmateLin
* Email: classmatelin.site@gmail.com
* Site: https://www.classmatelin.top
* @param string $filename 输出文件名
* @param int $batch 按多少批次生成数据
* @param int $batchSize 每批数据的大小
*/function generate(string $filename, int $batch=1000, int $batchSize=10000){
for ($i=0; $i<$batch; $i++) {
$str = '';
for ($j=0; $j<$batchSize; $j++) {
$str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
}
file_put_contents($filename, $str, FILE_APPEND); // 追加模式写入文件
}}generate('a.txt', 10);generate('b.txt', 10);分割文件
a.txt, b.txt通过hash取模的方式分割到n个文件中./**
* 用hash取模方式将文件分散到n个文件中
* Author: ClassmateLin
* Email: classmatelin.site@gmail.com
* Site: https://www.classmatelin.top
* @param string $filename 输入文件名
* @param int $mod 按mod取模
* @param string $dir 文件输出目录
*/
function spiltFile(string $filename, int $mod=20, string $dir='files')
{
if (!is_dir($dir)){
mkdir($dir);
}
$fp = fopen($filename, 'r');
while (!feof($fp)){
$line = fgets($fp);
$n = crc32(hash('md5', $line)) % $mod; // hash取模
$filepath = $dir . '/' . $n . '.txt'; // 文件输出路径
file_put_contents($filepath, $line, FILE_APPEND); // 追加模式写入文件
}
fclose($fp);
}
spiltFile('a.txt');
spiltFile('b.txt');执行splitFile函数, 得到如下图files
파일 채우기를 위한 난수 생성:
/**
* 查找一个文件中相同的记录输出到指定文件中
* Author: ClassmateLin
* Email: classmatelin.site@gmail.com
* Site: https://www.classmatelin.top
* @param string $inputFilename 输入文件路径
* @param string $outputFilename 输出文件路径
*/
function search(string $inputFilename, $outputFilename='output.txt')
{
$table = [];
$fp = fopen($inputFilename, 'r');
while (!feof($fp))
{
$line = fgets($fp);
!isset($table[$line]) ? $table[$line] = 1 : $table[$line]++; // 未设置的值设1，否则自增
}
fclose($fp);
foreach ($table as $line => $count)
{
if ($count >= 2){ // 出现大于2次的则是相同的记录，输出到指定文件中
file_put_contents($outputFilename, $line, FILE_APPEND);
}
}
}a.txt 변경 , b.txt는 해시 모듈러스에 의해 n개의 파일로 분할됩니다./**
* 从给定目录下文件中分别找出相同记录输出到指定文件中
* Author: ClassmateLin
* Email: classmatelin.site@gmail.com
* Site: https://www.classmatelin.top
* @param string $dirs 指定目录
* @param string $outputFilename 输出文件路径
*/
function searchAll($dirs='files', $outputFilename='output.txt')
{
$files = scandir($dirs);
foreach ($files as $file)
{
$filepath = $dirs . '/' . $file;
if (is_file($filepath)){
search($filepath, $outputFilename);
}
}
}splitFile 함수를 실행하고 아래와 같이 files 디렉터리를 가져옵니다. 20개 파일 중.
로그인 후 복사
위 내용은 PHP에서 두 개의 큰 파일에서 동일한 레코드를 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
