引言
給定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影片教學
