はじめに
それぞれ x 行と y 行のデータを含む 2 つのファイル a と b があるとします。ここで (x、y は両方ともより大きいです) 100 億)、マシンのメモリ制限は 100M です。同じレコードを見つけるにはどうすればよいですか?
感想
対処方法この問題の主な問題は、この膨大な量のデータを一度にメモリに読み込むことができないことです。
一度にメモリに読み込むことができない場合は、複数回検討されましたか？可能であれば、複数回読み取った後、同じ値を計算するにはどうすればよいですか?
分割統治思考を使用して、大きなものを小さなものに減らすことができます。ハッシュ後の同じ文字列の値が等しい場合は、ハッシュモジュロを使用してレコードを n 個のファイルに分散することを検討できます。これを取得するにはどうすればよいですか? PHP には 100M のメモリがあり、配列には約 100 万のデータを格納できるため、レコード a と b の行数が 10 億行しかないことを考慮すると、n は少なくとも 200 より大きくなければなりません。
現時点では 200 個のファイルがあります。同じレコードが同じファイル内に存在する必要があり、各ファイルはメモリに読み込むことができます。次に、これら 200 個のファイルから同じレコードを順番に検索し、同じファイルに出力すると、最終的に 2 つのファイル a と b に同じレコードが含まれます。
小さなファイル内で同じレコードを見つけるのは非常に簡単です。レコードの各行をハッシュ テーブルのキーとして使用し、キーの出現回数 >= 2 を数えます。 。
実際の操作
10 億ファイルは大きすぎます。実際の操作は時間の無駄です。実用的な目的を達成するだけです。
問題のサイズは次のように削減されます: 1M メモリ制限、a と b にはそれぞれ 100,000 行のレコードがあります。メモリ制限は 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ハッシュ係数によって 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');- Execute
SplitFile
関数は、以下に示すように、filesディレクトリ内の 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); } } }ログイン後にコピー
- 大規模ファイル処理のスペースの問題はこれまでに解決されましたが、時間の問題はどうすればよいでしょうか? 1 台のマシンでマルチコア処理を使用できます。 CPUが足りない場合は複数のサーバーを経由して処理することも可能です。
- 完全なコード
ログイン後にコピー
