引言
给定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的多外围解决，不够的话通过多台服务器解决。
残缺代码
<?phpini_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以取得更好的浏览体验。