PHP에서 두 개의 큰 파일에서 동일한 레코드를 찾는 방법은 무엇입니까?
- 慕斯앞으로
- 2021-06-23 11:32:382765검색
두 개의 파일 a와 b가 있고 각각 x 및 y 데이터 행이 있고(x, y는 모두 10억보다 큼) 머신 메모리 제한은 100M입니다. 이 문제를 해결하는데 가장 큰 어려움은 이 대용량 데이터를 한 번에 메모리에 읽을 수 없다는 것입니다. 한 번에 메모리에 읽을 수 없다면 여러 번 읽어도 될까요? 함께 토론해 봅시다
소개
두 개의 파일 a와 b가 있고 각각 x와 y 행의 데이터가 있다고 가정합니다. 여기서 (x, y는 모두 10억보다 큼) 머신 메모리 제한은 100M입니다. 같은 레코드가 무엇인지 알아보세요.
Things
이 문제를 처리할 때 가장 어려운 점은 이 대용량 데이터를 한 번에 메모리로 읽어들이는 것이 불가능하다는 것입니다.
읽을 수 없는 경우 한 번에 기억에 남는다면 여러 번 모직물로 간주할 수 있나요? 가능하다면 여러 번 읽어도 동일한 값을 어떻게 계산할 수 있습니까?
우리는 분할 정복 사고를 사용하여 큰 것을 작은 것으로 줄일 수 있습니다. 해싱 후 동일한 문자열의 값이 동일하면 해시 모듈로를 사용하여 레코드를 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개 파일 중.- 중복 레코드 찾기
🎜🎜모든 파일에서 동일한 레코드 찾기:🎜rrreee🎜🎜🎜대용량 파일 처리의 공간 문제는 지금까지 해결되었으므로 시간을 처리하는 방법은 무엇입니까? 문제가 있습니까? 단일 시스템에서 CPU의 멀티 코어 처리를 활용하면 충분하지 않은 경우 여러 서버에서 처리할 수 있습니다. 🎜🎜🎜🎜완전한 코드🎜rrreee🎜추천 학습: "🎜PHP 비디오 튜토리얼🎜"🎜위 내용은 PHP에서 두 개의 큰 파일에서 동일한 레코드를 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!