Contoh terperinci tentang cara PHP mencari rekod yang sama dalam dua fail besar

Artikel ini membawa anda pengetahuan yang berkaitan tentang PHP Memandangkan dua fail a dan b, masing-masing terdapat baris x dan y data, di mana (x, y kedua-duanya lebih besar daripada 1 bilion) , mesin. memori adalah terhad kepada 100M, bagaimana untuk mencari rekod yang sama Artikel ini akan menerangkan kaedah pelaksanaan, saya harap ia akan membantu semua orang.

(Tutorial disyorkan: Tutorial video PHP)

1 Pengenalan

Diberi dua a dan b di sana ialah dua fail, setiap satu dengan baris x dan y data (x, y kedua-duanya lebih besar daripada 1 bilion), dan memori mesin dihadkan kepada 100M Bagaimana untuk mencari rekod yang sama?

2

• Kesukaran utama dalam menangani masalah ini ialah mustahil untuk membaca data besar ini ke dalam ingatan pada satu masa
• Jika ia tidak boleh dibaca ke dalam ingatan pada satu masa masa, bolehkah ia dianggap beberapa kali? Jika boleh, bagaimana kita boleh mengira nilai yang sama selepas membacanya beberapa kali?
• Kita boleh menggunakan pemikiran divide and conquer untuk mengurangkan yang besar kepada yang kecil. Jika nilai rentetan yang sama adalah sama selepas pencincangan, maka kita boleh mempertimbangkan untuk menggunakan modulo cincang untuk menyuraikan rekod ke dalam n fail. Bagaimana untuk mendapatkan n ini? PHP mempunyai memori 100M, dan tatasusunan boleh menyimpan kira-kira 1 juta data Jadi memandangkan rekod a dan b hanya mempunyai 1 bilion baris, n mestilah sekurang-kurangnya lebih daripada 200.
• Terdapat 200 fail pada masa ini Rekod yang sama mesti berada dalam fail yang sama, dan setiap fail boleh dibaca ke dalam memori. Kemudian anda boleh mencari rekod yang sama dalam 200 fail ini secara bergilir-gilir, dan kemudian mengeluarkannya ke fail yang sama Hasil akhir ialah rekod yang sama dalam dua fail a dan b.
• Sangat mudah untuk mencari rekod yang sama dalam fail kecil Gunakan setiap baris rekod sebagai kunci jadual cincang dan kira bilangan kejadian kunci >= 2.

3. Operasi praktikal

1 bilion fail terlalu besar, dan operasi praktikal itu membuang masa sahaja.

Saiz masalah dikurangkan kepada: Had memori 1M, a dan b masing-masing mempunyai 100,000 baris rekod Had memori boleh dihadkan menggunakan ini_set('memory_limit', '1M'); PHP.

4. Jana fail ujian

Jana nombor rawak untuk mengisi fail:

/**
 * 生成随机数填充文件
 * 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 Pisahkan fail

akana.txt, b.txtPisah kepada n fail dengan modulus cincangan

/**
 * 用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');

Laksanakan fungsi splitFile dan dapatkan 20 fail dalam direktori files seperti yang ditunjukkan di bawah.

6. Cari rekod pendua

Sekarang kita perlu mencari rekod yang sama dalam 20 fail Malah, kita perlu mencari rekod yang sama dalam satu fail dan kendalikan setiap 20 kali.

Cari rekod yang sama dalam fail:

/**
 * 查找一个文件中相同的记录输出到指定文件中
 * 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);
        }
    }
}

Cari rekod yang sama dalam semua fail:

/**
 * 从给定目录下文件中分别找出相同记录输出到指定文件中
 * 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);
        }
    }
}

Setakat ini, masalah ruang pemprosesan fail besar telah diselesaikan, jadi bagaimana untuk menangani masalah masa? Satu mesin boleh diproses dengan menggunakan berbilang teras CPU Jika ia tidak mencukupi, ia boleh diproses oleh berbilang pelayan.

7. Kod lengkap

 (tutorial disyorkan: Tutorial video PHP)
Atas ialah kandungan terperinci Contoh terperinci tentang cara PHP mencari rekod yang sama dalam dua fail besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!