引言
给定a,b两个文件, 分别有x,y行数据, 其中(x, y均大于10亿), 机器内存限制100M,该如何找出其中相同的记录? php
思路
-
处理该问题的困难主要是没法将这海量数据一次性读内内存中.算法
-
一次性读不进内存中,那么是否能够考虑屡次呢?若是能够,那么屡次读入要怎么计算相同的值呢?数组
-
咱们能够用分治思想, 大而化小。相同字符串的值hash事后是相等的, 那么咱们能够考虑使用hash取模, 将记录分散到n个文件中。这个n怎么取呢? PHP 100M内存,数组大约能够存100w的数据, 那么按a,b记录都只有10亿行来算, n至少要大于200。服务器
-
此时有200个文件,相同的记录确定在同一个文件中,而且每一个文件均可以所有读进内存。那么能够依次找出这200个文件中各自相同的记录,而后输出到同一个文件中,获得的最终结果就是a, b两个文件中相同的记录。函数
-
找一个小文件中相同的记录很简单了吧,将每行记录做为hash表的key, 统计key的出现次数>=2就能够了。测试
实操
10亿各文件太大了,实操浪费时间,达到实践目的便可。spa
问题规模缩小为: 1M内存限制, a, b各有10w行记录, 内存限制能够用PHP的ini_set('memory_limit', '1M');
来限制。code
生成测试文件
生成随机数用于填充文件:内存
/** * 生成随机数填充文件 * 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次。md5
-
找一个文件中的相同记录:
/** * 查找一个文件中相同的记录输出到指定文件中 * 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');
title: PHP如何在两个大文件中找出相同的记录?
date: 2021-04-20 22:07:39
tags:
- 海量数据处理算法
- PHP
categories:
- 海量数据处理算法
引言
给定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');
来限制。
生成测试文件
生成随机数用于填充文件:
/** * 生成随机数填充文件 * 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');