乐趣区

关于php:PHP如何在两个大文件中找出相同的记录

jiezi

引言

给定 a，b 两个文件, 别离有 x，y 行数据, 其中(x, y 均大于 10 亿), 机器内存限度 100M，该如何找出其中雷同的记录?<!–more–>

思路

  • 解决该问题的艰难次要是无奈将这海量数据一次性读内内存中.
  • 一次性读不进内存中，那么是否能够思考屡次呢？如果能够，那么屡次读入要怎么计算雷同的值呢？
  • 咱们能够用分治思维，大而化小。雷同字符串的值 hash 过后是相等的, 那么咱们能够思考应用 hash 取模, 将记录扩散到 n 个文件中。这个 n 怎么取呢？PHP 100M 内存，数组大概能够存 100w 的数据, 那么按 a,b 记录都只有 10 亿行来算, n 至多要大于 200。
  • 此时有 200 个文件，雷同的记录必定在同一个文件中，并且每个文件都能够全副读进内存。那么能够顺次找出这 200 个文件中各自雷同的记录，而后输入到同一个文件中，失去的最终后果就是 a, b 两个文件中雷同的记录。
  • 找一个小文件中雷同的记录很简略了吧，将每行记录作为 hash 表的 key, 统计 key 的呈现次数 >= 2 就能够了。

实操

10 亿各文件太大了，实操浪费时间，达到实际目标即可。

问题规模放大为: 1M 内存限度, a, b 各有 10w 行记录, 内存限度能够用 PHP 的 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 目录的 20 个文件。

查找重复记录

当初须要查找 20 个文件中雷同的记录, 其实也就是找一个文件中的雷同记录，操作个 20 次。

  • 找一个文件中的雷同记录:

    /**
 * 查找一个文件中雷同的记录输入到指定文件中
 * 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 $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);
        }
    }
}
  • 到这里曾经解决了大文件解决的空间问题，那么工夫问题该如何解决? 单机可通过利用 CPU 的多外围解决，不够的话通过多台服务器解决。

残缺代码

<?php
ini_set('memory_limit', '1M'); // 内存限度 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);  // 追加模式写入文件
    }
}




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




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

// 生成文件
generate('a.txt', 10);
generate('b.txt', 10);

// 宰割文件
spiltFile('a.txt');
spiltFile('b.txt');

// 查找记录
searchAll('files', 'output.txt');
  • 欢送拜访集体博客: https://www.classmatelin.top 以取得更好的浏览体验。
退出移动版