How does PHP find the same records in two large files?
introduction
Given two files a and b, there are x and y rows of data, where (x, y are both greater than 1 billion), and the machine memory limit is 100M.How to find the same records?
Ideas
The main difficulty in dealing with this problem is the inability to read this massive amount of data into the internal memory at once.
Can't read into the memory at one time, so can it be considered multiple times? If so, how to calculate the same value for multiple readings?
We can use the idea of divide and conquer, big and small.The hash values of the same string are equal afterwards, so we can consider using hash modulo to disperse the records into n files.How to take this n? PHP 100M memory, the array can store about 100w of data, so if the records a and b are only 1 billion rows, n must be at least greater than 200.
At this time, there are 200 files, the same record must be in the same file, and each file can be read into the memory.Then you can find the same records in these 200 files in turn, and then output them to the same file.The final result is the same records in the two files a and b.
It is easy to find the same records in a small file.Use each record as the key of the hash table and count the number of occurrences of the key >=2.
Practice
The 1 billion files are too big, and the actual operation is a waste of time, just to achieve the practical purpose.
The size of the problem is reduced to: 1M memory limit, a and b each have 10w rows of records, the memory limit can be limited by PHP's ini_set('memory_limit', '1M');.
Generate test files
Generate random numbers to fill the file:
/** * Generate random number filling file * Author: ClassmateLin * Email: [email protected] * Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com * @param string $filename output file name * @param int $batch How many batches to generate data * @param int $batchSize The size of each batch of data */ 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; // Generate random numbers } file_put_contents($filename, $str, FILE_APPEND); // write file in append mode } } generate('a.txt', 10); generate('b.txt', 10);
Split file
Split a.txt and b.txt into n files by hashing.
/** * Scatter files into n files using hash modulo * Author: ClassmateLin * Email: [email protected] * Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com * @param string $filename input file name * @param int $mod mod by mod * @param string $dir file output directory */ 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 modulus $filepath = $dir.'/'. $n.'.txt'; // file output path file_put_contents($filepath, $line, FILE_APPEND); // write file in append mode } fclose($fp); } spiltFile('a.txt'); spiltFile('b.txt');
Execute the splitFile function to get 20 files in the files directory as shown below.
Find duplicate records
Now we need to find the same record in 20 files.In fact, it means to find the same record in one file and operate it 20 times.
Find the same record in a file:
/** * Find the same record in a file and output it to the specified file * Author: ClassmateLin * Email: [email protected] * Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com * @param string $inputFilename input file path * @param string $outputFilename output file path */ 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]++; // The unset value is set to 1, otherwise it will be incremented } fclose($fp); foreach ($table as $line => $count) { if ($count >= 2){ // The same record that appears more than 2 times is output to the specified file file_put_contents($outputFilename, $line, FILE_APPEND); } } }
Find the same records in all files:
/** * Find the same records from the files in the given directory and output them to the specified file * Author: ClassmateLin * Email: [email protected] * Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com * @param string $dirs specify the directory * @param string $outputFilename output file path */ function searchAll($dirs='files', $outputFilename='output.txt') { $files = scandir($dirs); foreach ($files as $file) { $filepath = $dirs.'/'. $file; if (is_file($filepath)){ search($filepath, $outputFilename); } } }
So far, the space problem of large file processing has been solved, so how to deal with the time problem? A single machine can use the multi-core processing of the CPU, if not enough, it can be processed by multiple servers.
Complete code
<?php
ini_set('memory_limit', '1M'); // memory limit 1M
/**
* Generate random number filling file
* Author: ClassmateLin
* Email: [email protected]
* Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com
* @param string $filename output file name
* @param int $batch How many batches to generate data
* @param int $batchSize The size of each batch of data
*/
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; // Generate random numbers
}
file_put_contents($filename, $str, FILE_APPEND); // write file in append mode
}
}
/**
* Scatter files into n files using hash modulo
* Author: ClassmateLin
* Email: [email protected]
* Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com
* @param string $filename input file name
* @param int $mod mod by mod
* @param string $dir file output directory
*/
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 modulus
$filepath = $dir.'/'. $n.'.txt'; // file output path
file_put_contents($filepath, $line, FILE_APPEND); // write file in append mode
}
fclose($fp);
}
/**
* Find the same record in a file and output it to the specified file
* Author: ClassmateLin
* Email: [email protected]
* Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com
* @param string $inputFilename input file path
* @param string $outputFilename output file path
*/
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]++; // The unset value is set to 1, otherwise it will be incremented
}
fclose($fp);
foreach ($table as $line => $count)
{
if ($count >= 2){ // The same record that appears more than 2 times is output to the specified file
file_put_contents($outputFilename, $line, FILE_APPEND);
}
}
}
/**
* Find the same records from the files in the given directory and output them to the specified file
* Author: ClassmateLin
* Email: [email protected]
* Site: https://classmatelin-1258942535.cos-website.ap-hongkong.myqcloud.com
* @param string $dirs specify the directory
* @param string $outputFilename output file path
*/
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 file
generate('a.txt', 10);
generate('b.txt', 10);
// Split file
spiltFile('a.txt');
spiltFile('b.txt');
// Find records
searchAll('files','output.txt');Tags
Technical otaku
Sought technology together
Related Topic
51 Comments
& lt;a href=https://gazeta-echo.ru/sekrety-diagnostiki-i-remonta-noutbukov/& gt;ремонт ноутбуков asus& lt;/a& gt; & lt;a href="http://kfaktiv.ru/kak-vybrat-mastera-po-remontu-noutbukov.html"& gt;ремонт ноутбуков asus& lt;/a& gt;
Charleselund
2022-08-16
& lt;a href=https://stroim-doma-rf.ru/& gt;готовый дом под ключ& lt;/a& gt; & lt;a href=http://stroim-doma-rf.ru/& gt;https://stroim-doma-rf.ru& lt;/a& gt; & lt;a href=http://www.google.ro/url?q=https://stroim-doma-rf.ru/& gt;https://google.mu/url?q=https://stroim-doma-rf.ru/& lt;/a& gt;
FrancisWeerb
2022-08-14
& lt;a href=https://autoru-otzyv.ru/otzyvy-avtosalon/abc-auto/& gt;abc auto автосалон отзывы покупателей& lt;/a& gt; & lt;a href=http://autoru-otzyv.ru/otzyvy-avtosalon/abc-auto/& gt;http://www.autoru-otzyv.ru/otzyvy-avtosalon/abc-auto& lt;/a& gt; & lt;a href=https://www.google.de/url?q=https://autoru-otzyv.ru/otzyvy-avtosalon/abc-auto/& gt;https://google.pt/url?q=https://autoru-otzyv.ru/otzyvy-avtosalon/abc-auto/& lt;/a& gt;
Hectorhurry
2022-08-13
& lt;a href=https://hi-servis.ru/& gt;ремонт компьютеров химки& lt;/a& gt; & lt;a href=http://www.hi-servis.ru& gt;http://hi-servis.ru& lt;/a& gt; & lt;a href=https://www.2898.com/whois/https://hi-servis.ru/& gt;http://google.tm/url?q=https://hi-servis.ru/& lt;/a& gt;
SteverAlecy
2022-08-12
& lt;a href=https://futuramia.ru/program/igra-v-kalmara/& gt;https://futuramia.ru/& lt;/a& gt; & lt;a href=https://futuramia.ru/program/akvaramiya/& gt;https://futuramia.ru/program/vypusti-zverya-vypusknoj-4j-klass/& lt;/a& gt; & lt;a href=https://www.google.tm/url?q=https://futuramia.ru/& gt;http://www.google.mn/url?q=https://futuramia.ru/& lt;/a& gt;
Mathewson
2022-08-11
& lt;a href=https://mobileax.ru/& gt;как выйти из apple music на iphone& lt;/a& gt; & lt;a href=http://www.mobileax.ru& gt;http://mobileax.ru& lt;/a& gt; & lt;a href=https://freebacklinks.ru/site?url=https://mobileax.ru/& gt;http://tootoo.to/op/?redirect=https://mobileax.ru/& lt;/a& gt;
FrancisFam
2022-08-11
& lt;a href=https://eroticheskiy-massage-kazan.ru& gt;эротические массаж казань индивидуальный& lt;/a& gt; & lt;a href=http://eroticheskiy-massage-kazan.ru/& gt;http://www.eroticheskiy-massage-kazan.ru& lt;/a& gt; & lt;a href=http://www.google.mu/url?q=https://eroticheskiy-massage-kazan.ru& gt;http://www.google.mw/url?q=https://eroticheskiy-massage-kazan.ru& lt;/a& gt;
Briceadugs
2022-08-10
& lt;a href=https://eroticheskiy-massage-kazan.ru& gt;дамский угодник салон эротического массажа казань& lt;/a& gt; & lt;a href=http://eroticheskiy-massage-kazan.ru& gt;https://eroticheskiy-massage-kazan.ru/& lt;/a& gt; & lt;a href=http://google.com.na/url?q=https://eroticheskiy-massage-kazan.ru& gt;http://www.google.bf/url?q=https://eroticheskiy-massage-kazan.ru& lt;/a& gt;
Briceadugs
2022-08-10
& lt;a href=https://prodvizhenie-saitov-24.ru/& gt;продвижение сайта топ яндекса цена& lt;/a& gt; & lt;a href=http://prodvizhenie-saitov-24.ru& gt;https://www.prodvizhenie-saitov-24.ru/& lt;/a& gt; & lt;a href=https://joomlinks.org/?url=https://prodvizhenie-saitov-24.ru/& gt;http://google.com.ec/url?q=https://prodvizhenie-saitov-24.ru/& lt;/a& gt;
WarrenPhobe
2022-08-09
& lt;a href=http://lex-center.ru/?page_id=933& gt;как освободить мужа из колонии раньше времени,& lt;/a& gt; & lt;a href=http://www.lex-center.ru/& gt;http://www.lex-center.ru/& lt;/a& gt; & lt;a href=http://www.google.mw/url?q=http://lex-center.ru/& gt;http://www.google.ru/url?q=http://lex-center.ru/& lt;/a& gt;
RobertWar
2022-08-06
& lt;a href=https://urflex.ru/arbitrazhnyy-yurist.html& gt;Регистрация общественной организации& lt;/a& gt; & lt;a href=https://www.urflex.ru& gt;http://urflex.ru& lt;/a& gt; & lt;a href=http://www.google.tg/url?q=https://urflex.ru/& gt;http://pin.anime.com/source/https://urflex.ru/& lt;/a& gt;
Jasonfus
2022-08-05
& lt;a href=https://prodvizhenie-saitov-24.ru/& gt;продвижение интернет магазина недорого& lt;/a& gt; & lt;a href=http://prodvizhenie-saitov-24.ru/& gt;http://www.prodvizhenie-saitov-24.ru& lt;/a& gt; & lt;a href=http://www.dogjudge.com/?URL=https://prodvizhenie-saitov-24.ru/& gt;https://anolink.com/?link=https://prodvizhenie-saitov-24.ru/& lt;/a& gt;
WarranPhobe
2022-08-05
& lt;a href=https://stroim-doma-rf.ru/& gt;дом каркасный под ключ& lt;/a& gt; & lt;a href=https://stroim-doma-rf.ru/& gt;http://www.stroim-doma-rf.ru& lt;/a& gt; & lt;a href=http://www.google.ps/url?q=https://stroim-doma-rf.ru/& gt;http://www.google.ga/url?q=https://stroim-doma-rf.ru/& lt;/a& gt;
FrancisWeerb
2022-08-03
& lt;a href=https://stroim-doma-rf.ru/& gt;построить дом каркасный& lt;/a& gt; & lt;a href=http://www.stroim-doma-rf.ru& gt;https://www.stroim-doma-rf.ru& lt;/a& gt; & lt;a href=http://www.9998494.ru/R.ashx?s=https://stroim-doma-rf.ru/& gt;https://google.hr/url?q=https://stroim-doma-rf.ru/& lt;/a& gt;
FrancisWeerb
2022-08-02
& lt;a href=https://dorog-asfaltirovanie.ru/& gt;асфальтирование дорог& lt;/a& gt; & lt;a href=http://www.dorog-asfaltirovanie.ru& gt;http://dorog-asfaltirovanie.ru& lt;/a& gt; & lt;a href=https://www.google.dk/url?q=https://dorog-asfaltirovanie.ru/& gt;http://www.silverdart.co.uk/?URL=https://dorog-asfaltirovanie.ru/& lt;/a& gt;
DavidTwect
2022-07-28
& lt;a href=https://dorog-asfaltirovanie.ru/& gt;сколько стоит асфальтирование дороги 1 км& lt;/a& gt; & lt;a href=https://dorog-asfaltirovanie.ru& gt;https://www.dorog-asfaltirovanie.ru& lt;/a& gt; & lt;a href=https://google.md/url?q=https://dorog-asfaltirovanie.ru/& gt;http://google.tk/url?q=https://dorog-asfaltirovanie.ru/& lt;/a& gt;
DavidTwect
2022-07-28
& lt;a href=http://specodegdaoptom.ru/& gt;магазины спецодежды в москве рядом со мной& lt;/a& gt; & lt;a href=http://www.specodegdaoptom.ru/& gt;http://specodegdaoptom.ru& lt;/a& gt; & lt;a href=http://www.google.sm/url?q=http://specodegdaoptom.ru/& gt;http://google.co.ao/url?q=http://specodegdaoptom.ru/& lt;/a& gt;
Alfonsojef
2022-07-26
& lt;a href=https://www.litprichal.ru/press/311/& gt;Елена Лихач муж& lt;/a& gt; & lt;a href=http://litprichal.ru/press/311/& gt;http://www.litprichal.ru/press/311/& lt;/a& gt; & lt;a href=http://google.co.zm/url?q=https://www.litprichal.ru/press/311/& gt;https://google.sc/url?q=https://www.litprichal.ru/press/311/& lt;/a& gt;
JohnnieRed
2022-07-24
& lt;a href=http://www.kremlinrus.ru/article/455/151796/& gt;Елена Лихач жена& lt;/a& gt; & lt;a href=https://www.kremlinrus.ru/article/455/151796/& gt;https://www.kremlinrus.ru/article/455/151796/& lt;/a& gt; & lt;a href=https://cse.google.ie/url?q=http://www.kremlinrus.ru/article/455/151796/& gt;https://www.google.pl/url?q=http://www.kremlinrus.ru/article/455/151796/& lt;/a& gt;
EduardoDrupt
2022-07-18
& lt;a href=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;официальный дилер республика авто отзывы& lt;/a& gt; & lt;a href=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;http://www.autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& lt;/a& gt; & lt;a href=https://rivannamusic.com/?URL=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;http://www.google.hr/url?q=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& lt;/a& gt;
Davidwhero
2022-07-16
& lt;a href=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;официальный дилер республика отзывы& lt;/a& gt; & lt;a href=http://www.autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;https://www.autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& lt;/a& gt; & lt;a href=http://znaigorod.ru/away?to=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& gt;https://www.hogodoc.com/?URL=https://autoru-otzyv.ru/otzyvy-avtosalon/respublika-auto/& lt;/a& gt;
Davidwhero
2022-07-16
& lt;a href=https://toyotyres.site/& gt;купить toyo& lt;/a& gt; & lt;a href=http://toyotyres.site/& gt;http://toyotyres.site/& lt;/a& gt; & lt;a href=http://www.scsa.ca/?URL=https://toyotyres.site/& gt;http://s.z-z.jp/c.cgi?https://toyotyres.site/& lt;/a& gt;
Stevennot
2022-07-10
& lt;a href=https://suhoj-led-msk.ru/& gt;сухой лед ивантеевка& lt;/a& gt; & lt;a href=https://www.suhoj-led-msk.ru& gt;https://suhoj-led-msk.ru/& lt;/a& gt; & lt;a href=https://backlinks.ssylki.info/links.php?link=https://suhoj-led-msk.ru/& gt;http://www.pahu.de/url?q=https://suhoj-led-msk.ru/& lt;/a& gt;
Danielwheft
2022-07-01
& lt;a href=https://upjobs.ru/articles/view/823.html& gt;обучение персонала& lt;/a& gt; & lt;a href=https://osobye.ru/blogs/raznye-stati/rekrutingovaja-kompanija-v-minske.html& gt;http://www.nokia.bir.ru/forum/index.php?showtopic=759400& lt;/a& gt; & lt;a href=https://www.google.sm/url?q=https://adminresurs.by/& gt;https://www.wilsonlearning.com/?URL=https://adminresurs.by/& lt;/a& gt;
Cesarmut
2022-06-21
& lt;a href=https://www.regionles35.ru& gt;брус заказать& lt;/a& gt; & lt;a href=http://regionles35.ru& gt;http://regionles35.ru& lt;/a& gt; & lt;a href=http://google.bi/url?q=http://regionles35.ru& gt;http://cse.google.ch/url?q=http://regionles35.ru& lt;/a& gt;
RafaelRAH
2022-06-14
& lt;a href=http://center-tec.ru/index6.html& gt;курсы переподготовки пожарная безопасность& lt;/a& gt; & lt;a href=http://center-tec.ru/index6.html& gt;http://center-tec.ru/index6.html& lt;/a& gt; & lt;a href=http://google.com.af/url?q=http://center-tec.ru/index6.html& gt;https://www.google.kz/url?q=http://center-tec.ru/index6.html& lt;/a& gt;
IsmaelKer
2022-06-10
& lt;a href=http://center-tec.ru/index6.html& gt;пожарная безопасность повышение квалификации для руководителей& lt;/a& gt; & lt;a href=http://www.center-tec.ru/index6.html& gt;http://center-tec.ru/index6.html& lt;/a& gt; & lt;a href=http://www.google.sm/url?q=http://center-tec.ru/index6.html& gt;https://www.google.ki/url?q=http://center-tec.ru/index6.html& lt;/a& gt;
IsmaelKer
2022-06-08
& lt;a href=http://vds33.ru& gt;пиломатериалы спб от производителя& lt;/a& gt; & lt;a href=http://vds33.ru/& gt;http://vds33.ru/& lt;/a& gt; & lt;a href=http://marcellospizzapasta.com/?URL=vds33.ru& gt;http://www.google.tk/url?q=http://vds33.ru& lt;/a& gt;
Kennethmit
2022-06-07
& lt;a href=https://www.indigo-school.ru& gt;английский для детей онлайн& lt;/a& gt; & lt;a href=https://indigo-school.ru& gt;https://indigo-school.ru& lt;/a& gt; & lt;a href=http://google.com.sv/url?q=http://indigo-school.ru& gt;https://rivannamusic.com/?URL=indigo-school.ru& lt;/a& gt;
JamessperM
2022-05-30
& lt;a href=http://english-yes.ru& gt;полиглотики спб& lt;/a& gt; & lt;a href=http://english-yes.ru/& gt;http://english-yes.ru/& lt;/a& gt; & lt;a href=http://www.google.ru/url?q=http://english-yes.ru& gt;http://www.lycocard.com/?URL=english-yes.ru& lt;/a& gt;
Boriskzepsy
2022-05-29
& lt;a href=https://english-yes.ru& gt;развитие речи& lt;/a& gt; & lt;a href=http://english-yes.ru/& gt;http://english-yes.ru/& lt;/a& gt; & lt;a href=http://whois.desta.biz/whois/english-yes.ru& gt;http://google.co.il/url?q=http://english-yes.ru& lt;/a& gt;
Boriskzepsy
2022-05-26
& lt;a href=https://school-of-languages.ru/& gt;китайский для детей& lt;/a& gt; & lt;a href=https://school-of-languages.ru& gt;https://school-of-languages.ru& lt;/a& gt; & lt;a href=https://google.rs/url?q=http://school-of-languages.ru& gt;https://a.pr-cy.ru/school-of-languages.ru& lt;/a& gt;
JamesBruic
2022-05-25
& lt;a href=https://avto-dublikat.ru/& gt;иностранные гос номера& lt;/a& gt; & lt;a href=http://avto-dublikat.ru/& gt;https://www.avto-dublikat.ru/& lt;/a& gt; & lt;a href=http://cse.google.be/url?q=https://avto-dublikat.ru/& gt;http://www.google.bi/url?q=https://avto-dublikat.ru/& lt;/a& gt; https://www.avto-dublikat.ru/
Jamesapose
2022-05-20
& lt;a href=https://avto-dublikat.ru/& gt;сувенирные номера на авто& lt;/a& gt; & lt;a href=http://avto-dublikat.ru/& gt;http://www.avto-dublikat.ru/& lt;/a& gt; & lt;a href=http://www.google.rw/url?q=https://avto-dublikat.ru/& gt;http://cse.google.at/url?q=https://avto-dublikat.ru/& lt;/a& gt; https://avto-dublikat.ru/
Jamesapose
2022-05-20
& lt;a href=https://proxyspace.seo-hunter.com/mobile-proxies/kalach/& gt;proxy for registration in social networks& lt;/a& gt;
Norbetger
2022-01-30
& lt;a href=https://prodvizhenie-online.ru/& gt;заказать продвижение сайта в топ& lt;/a& gt; & lt;a href=https://prodvizhenie-online.ru/& gt;http://prodvizhenie-online.ru/& lt;/a& gt; & lt;a href=https://www.google.hu/url?q=https://prodvizhenie-online.ru/& gt;http://www.google.be/url?q=https://prodvizhenie-online.ru/& lt;/a& gt;
WartenPhobe
2022-08-16