PHP가 두 개의 큰 파일에서 동일한 레코드를 찾는 방법에 대한 자세한 예

이 기사에서는 PHP에 대한 관련 지식을 제공합니다. 두 개의 파일 a와 b가 있고 각각 x와 y 행의 데이터가 있고(x와 y는 모두 10억보다 큼) 머신 메모리 제한은 100M입니다. 이 글은 모든 사람에게 구현 방법을 설명할 것입니다.

(권장 튜토리얼: PHP 비디오 튜토리얼)

1. 소개

두 개의 파일 a와 b가 있고 각각 x와 y 행의 데이터가 있습니다. 여기서 (x, y는 모두 10억보다 큽니다) , 기계 메모리는 100M로 제한되어 있는데, 동일한 레코드를 찾는 방법은 무엇입니까?

이 문제를 처리할 때 가장 어려운 점은 이 엄청난 양의 데이터를 한 번에 메모리로 읽을 수 없다는 것입니다.

한 번에 메모리에 읽어올 수 없는 경우 여러 번 고려할 수 있나요? 가능하다면 여러 번 읽어도 동일한 값을 어떻게 계산할 수 있습니까?
• 우리는 분할 정복 사고를 사용하여 큰 것을 작은 것으로 줄일 수 있습니다. 해싱 후 동일한 문자열의 값이 동일하면 해시 모듈러스를 사용하여 레코드를 n개의 파일로 분산시키는 것을 고려할 수 있습니다. 이 n을 얻는 방법? PHP에는 1억 개의 메모리가 있고 배열은 약 1백만 개의 데이터를 저장할 수 있습니다. 따라서 레코드 a와 b에 10억 개의 행만 있다는 점을 고려하면 n은 최소한 200보다 커야 합니다.
• 이때 파일은 200개입니다. 동일한 레코드가 동일한 파일에 있어야 하며 각 파일을 메모리로 읽어올 수 있습니다. 그러면 이 200개의 파일에서 동일한 레코드를 순서대로 찾은 다음 동일한 파일로 출력할 수 있습니다. 최종 결과는 두 파일 a와 b에서 동일한 레코드입니다.
• 작은 파일에서 동일한 레코드를 찾는 것은 쉽습니다. 레코드의 각 행을 해시 테이블의 키로 사용하고 키의 발생 횟수를 2 이상으로 계산하면 됩니다.
• 3. 실용적인 작업

10억 개의 파일은 너무 크고, 실제적인 작업은 시간 낭비입니다.

문제 크기는 다음과 같이 줄어듭니다. 메모리 제한은 1M이며, a와 b는 각각 100,000행의 레코드를 갖습니다. 메모리 제한은 PHP의 ini_set('memory_limit', '1M');로 제한할 수 있습니다.

4. 테스트 파일 생성

ini_set('memory_limit', '1M');来限制。

4、生成测试文件

生成随机数用于填充文件:

/**
 * 生成随机数填充文件
 * 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 = &#39;&#39;;
        for ($j=0; $j<$batchSize; $j++) {
            $str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
        }
        file_put_contents($filename, $str, FILE_APPEND);  // 追加模式写入文件
    }
}

generate(&#39;a.txt&#39;, 10);
generate(&#39;b.txt&#39;, 10);

5、分割文件

将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);
        }
    }
}

5. 파일을 분할합니다

해시 a.txt, b.txt 분할

/**
 * 从给定目录下文件中分别找出相同记录输出到指定文件中
 * 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개의 파일을 가져옵니다.

6. 중복 레코드 찾기

이제 20개의 파일에서 동일한 레코드를 찾아야 합니다. 실제로 하나의 파일에서 동일한 레코드를 찾아 20번 작업해야 합니다.

파일에서 동일한 레코드 찾기:

모든 파일에서 동일한 레코드 찾기:rrreee이제 대용량 파일 처리의 공간 문제가 해결되었으니 단일 머신에서 시간 문제를 어떻게 처리할 수 있을까요? CPU 처리가 멀티코어로 충분하지 않으면 여러 서버를 통해 처리됩니다. 
🎜7. 완전한 코드🎜rrreee🎜(추천 튜토리얼: 🎜PHP 비디오 튜토리얼🎜)🎜
위 내용은 PHP가 두 개의 큰 파일에서 동일한 레코드를 찾는 방법에 대한 자세한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!