当前位置：Gxlcms > PHP教程 > PHP如何在两个大文件中找出相同的记录?

PHP如何在两个大文件中找出相同的记录?

时间：2021-07-01 10:21:17 帮助过：9人阅读

给定a，b两个文件, 分别有x，y行数据, 其中(x, y均大于10亿), 机器内存限制100M，该如何找出其中相同的记录?思路处理该问题的困难主要是无法将这海量数据一次性读内内存中.一次性读不进内存中，那么是否可以考虑多次呢？我们一起探讨吧

引言

给定a，b两个文件, 分别有x，y行数据, 其中(x, y均大于10亿), 机器内存限制100M，该如何找出其中相同的记录?

思路

  • 处理该问题的困难主要是无法将这海量数据一次性读内内存中.

  • 一次性读不进内存中，那么是否可以考虑多次呢？如果可以，那么多次读入要怎么计算相同的值呢？

  • 我们可以用分治思想， 大而化小。相同字符串的值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');来限制。

生成测试文件

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

  1. /**
  2.  * 生成随机数填充文件
  3.  * Author: ClassmateLin
  4.  * Email: classmatelin.site@gmail.com
  5.  * Site: https://www.classmatelin.top
  6.  * @param string $filename 输出文件名
  7.  * @param int $batch 按多少批次生成数据
  8.  * @param int $batchSize 每批数据的大小
  9.  */function generate(string $filename, int $batch=1000, int $batchSize=10000){
  10.     for ($i=0; $i<$batch; $i++) {
  11.         $str = '';
  12.         for ($j=0; $j<$batchSize; $j++) {
  13.             $str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
  14.         }
  15.         file_put_contents($filename, $str, FILE_APPEND);  // 追加模式写入文件
  16.     }}generate('a.txt', 10);generate('b.txt', 10);

分割文件

  • 将a.txt, b.txt通过hash取模的方式分割到n个文件中.
  1. /**
  2.  * 用hash取模方式将文件分散到n个文件中
  3.  * Author: ClassmateLin
  4.  * Email: classmatelin.site@gmail.com
  5.  * Site: https://www.classmatelin.top
  6.  * @param string $filename 输入文件名
  7.  * @param int $mod 按mod取模
  8.  * @param string $dir 文件输出目录
  9.  */
  10. function spiltFile(string $filename, int $mod=20, string $dir='files')
  11. {
  12.     if (!is_dir($dir)){
  13.         mkdir($dir);
  14.     }
  15.     $fp = fopen($filename, 'r');
  16.     while (!feof($fp)){
  17.         $line = fgets($fp);
  18.         $n = crc32(hash('md5', $line)) % $mod; // hash取模
  19.         $filepath = $dir . '/' . $n . '.txt';  // 文件输出路径
  20.         file_put_contents($filepath, $line, FILE_APPEND); // 追加模式写入文件
  21.     }
  22.     fclose($fp);
  23. }
  24. spiltFile('a.txt');
  25. spiltFile('b.txt');

执行splitFile函数, 得到如下图files目录的20个文件。

查找重复记录

现在需要查找20个文件中相同的记录, 其实也就是找一个文件中的相同记录，操作个20次。

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

    1. /**
    2.  * 查找一个文件中相同的记录输出到指定文件中
    3.  * Author: ClassmateLin
    4.  * Email: classmatelin.site@gmail.com
    5.  * Site: https://www.classmatelin.top
    6.  * @param string $inputFilename 输入文件路径
    7.  * @param string $outputFilename 输出文件路径
    8.  */
    9. function search(string $inputFilename, $outputFilename='output.txt')
    10. {
    11.     $table = [];
    12.     $fp = fopen($inputFilename, 'r');
    13.     while (!feof($fp))
    14.     {
    15.         $line = fgets($fp);
    16.         !isset($table[$line]) ? $table[$line] = 1 : $table[$line]++; // 未设置的值设1，否则自增
    17.     }
    18.     fclose($fp);
    19.     foreach ($table as $line => $count)
    20.     {
    21.         if ($count >= 2){ // 出现大于2次的则是相同的记录，输出到指定文件中
    22.             file_put_contents($outputFilename, $line, FILE_APPEND);
    23.         }
    24.     }
    25. }

  • 找出所有文件相同记录:

    1. /**
    2.  * 从给定目录下文件中分别找出相同记录输出到指定文件中
    3.  * Author: ClassmateLin
    4.  * Email: classmatelin.site@gmail.com
    5.  * Site: https://www.classmatelin.top
    6.  * @param string $dirs 指定目录
    7.  * @param string $outputFilename 输出文件路径
    8.  */
    9. function searchAll($dirs='files', $outputFilename='output.txt')
    10. {
    11.     $files = scandir($dirs);
    12.     foreach ($files as $file)
    13.     {
    14.         $filepath = $dirs . '/' . $file;
    15.         if (is_file($filepath)){
    16.             search($filepath, $outputFilename);
    17.         }
    18.     }
    19. }

  • 到这里已经解决了大文件处理的空间问题，那么时间问题该如何处理? 单机可通过利用CPU的多核心处理，不够的话通过多台服务器处理。

完整代码

  1. <?php
  2. ini_set('memory_limit', '1M'); // 内存限制1M
  3. /**
  4.  * 生成随机数填充文件
  5.  * Author: ClassmateLin
  6.  * Email: classmatelin.site@gmail.com
  7.  * Site: https://www.classmatelin.top
  8.  * @param string $filename 输出文件名
  9.  * @param int $batch 按多少批次生成数据
  10.  * @param int $batchSize 每批数据的大小
  11.  */
  12. function generate(string $filename, int $batch=1000, int $batchSize=10000)
  13. {
  14.     for ($i=0; $i<$batch; $i++) {
  15.         $str = '';
  16.         for ($j=0; $j<$batchSize; $j++) {
  17.             $str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
  18.         }
  19.         file_put_contents($filename, $str, FILE_APPEND);  // 追加模式写入文件
  20.     }
  21. }
  22. /**
  23.  * 用hash取模方式将文件分散到n个文件中
  24.  * Author: ClassmateLin
  25.  * Email: classmatelin.site@gmail.com
  26.  * Site: https://www.classmatelin.top
  27.  * @param string $filename 输入文件名
  28.  * @param int $mod 按mod取模
  29.  * @param string $dir 文件输出目录
  30.  */
  31. function spiltFile(string $filename, int $mod=20, string $dir='files')
  32. {
  33.     if (!is_dir($dir)){
  34.         mkdir($dir);
  35.     }
  36.     $fp = fopen($filename, 'r');
  37.     while (!feof($fp)){
  38.         $line = fgets($fp);
  39.         $n = crc32(hash('md5', $line)) % $mod; // hash取模
  40.         $filepath = $dir . '/' . $n . '.txt';  // 文件输出路径
  41.         file_put_contents($filepath, $line, FILE_APPEND); // 追加模式写入文件
  42.     }
  43.     fclose($fp);
  44. }
  45. /**
  46.  * 查找一个文件中相同的记录输出到指定文件中
  47.  * Author: ClassmateLin
  48.  * Email: classmatelin.site@gmail.com
  49.  * Site: https://www.classmatelin.top
  50.  * @param string $inputFilename 输入文件路径
  51.  * @param string $outputFilename 输出文件路径
  52.  */
  53. function search(string $inputFilename, $outputFilename='output.txt')
  54. {
  55.     $table = [];
  56.     $fp = fopen($inputFilename, 'r');
  57.     while (!feof($fp))
  58.     {
  59.         $line = fgets($fp);
  60.         !isset($table[$line]) ? $table[$line] = 1 : $table[$line]++; // 未设置的值设1，否则自增
  61.     }
  62.     fclose($fp);
  63.     foreach ($table as $line => $count)
  64.     {
  65.         if ($count >= 2){ // 出现大于2次的则是相同的记录，输出到指定文件中
  66.             file_put_contents($outputFilename, $line, FILE_APPEND);
  67.         }
  68.     }
  69. }
  70. /**
  71.  * 从给定目录下文件中分别找出相同记录输出到指定文件中
  72.  * Author: ClassmateLin
  73.  * Email: classmatelin.site@gmail.com
  74.  * Site: https://www.classmatelin.top
  75.  * @param string $dirs 指定目录
  76.  * @param string $outputFilename 输出文件路径
  77.  */
  78. function searchAll($dirs='files', $outputFilename='output.txt')
  79. {
  80.     $files = scandir($dirs);
  81.     foreach ($files as $file)
  82.     {
  83.         $filepath = $dirs . '/' . $file;
  84.         if (is_file($filepath)){
  85.             search($filepath, $outputFilename);
  86.         }
  87.     }
  88. }
  89. // 生成文件
  90. generate('a.txt', 10);
  91. generate('b.txt', 10);
  92. // 分割文件
  93. spiltFile('a.txt');
  94. spiltFile('b.txt');
  95. // 查找记录
  96. searchAll('files', 'output.txt');

推荐学习：《PHP视频教程》

以上就是PHP如何在两个大文件中找出相同的记录?的详细内容，更多请关注gxlcms其它相关文章！

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！