소개
두 개의 파일 a와 b가 있고 각각 x 및 y 데이터 행이 있고(x, y는 모두 10억보다 큼) 머신 메모리 제한은 100M입니다. 동일한 레코드를 찾는 방법 ?
Thoughts
이 문제를 처리할 때 가장 어려운 점은 이 대용량 데이터를 한 번에 메모리로 읽을 수 없다는 것입니다.
그렇지 않으면 한 번에 메모리에 읽어 들인 다음 여러 번 고려하는 것이 가능합니까? 가능하다면 여러 번 읽어도 동일한 값을 어떻게 계산할 수 있습니까?
우리는 분할 정복 사고를 사용하여 큰 것을 작은 것으로 줄일 수 있습니다. 해싱 후 동일한 문자열의 값이 동일하면 해시 모듈로를 사용하여 레코드를 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);
}
}
}로그인 후 복사
파일 분할/**
* 查找一个文件中相同的记录输出到指定文件中
* 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개의 파일을 가져옵니다.
- 이제 20개의 파일에서 동일한 레코드를 찾아야 합니다. 실제로 하나의 파일에서 동일한 레코드를 찾아 20번 작업해야 합니다.
로그인 후 복사
