PHP が 2 つの大きなファイル内で同じレコードを検索する方法の詳細な例

この記事では、PHP に関する関連知識を提供します。2 つのファイル a と b があるとすると、それぞれ x 行と y 行のデータがあり、(x、y は両方とも 10 億より大きい)、マシンメモリが 100M に制限されている場合、同じレコードを見つけるにはどうすればよいですか? この記事では実装方法を説明しますので、皆様のお役に立てれば幸いです。

(推奨チュートリアル: PHP ビデオ チュートリアル)

1. はじめに

2 つの a と b があるとします。それぞれ x 行と y 行のデータを含むファイルです (x と y は両方とも 10 億を超えています)。マシンのメモリは 100M に制限されています。同じレコードを見つける方法は?

2. アイデア

• この問題に対処する際の難しさは、主に、この膨大なデータを一度にメモリに読み込むことができないことです。
• 一度にメモリに読み込むことができない場合は、それは複数回考慮されますか？可能であれば、複数回読み取った後、同じ値を計算するにはどうすればよいですか?
• 分割統治思考を使用して、大きなものを小さなものに減らすことができます。ハッシュ後の同じ文字列の値が等しい場合は、ハッシュモジュロを使用してレコードを n 個のファイルに分散することを検討できます。これを取得するにはどうすればよいですか? PHP には 100M のメモリがあり、配列には約 100 万のデータを格納できるため、レコード a と b の行数が 10 億行しかないことを考慮すると、n は少なくとも 200 より大きくなければなりません。
• 現時点ではファイルが 200 個あります。同じレコードが同じファイル内に存在する必要があり、各ファイルはメモリに読み込むことができます。次に、これら 200 個のファイルから同じレコードを順番に検索し、同じファイルに出力すると、最終的に 2 つのファイル a と b に同じレコードが含まれます。
• 小さなファイル内で同じレコードを見つけるのは非常に簡単です。レコードの各行をハッシュ テーブルのキーとして使用し、キーが 2 以上出現する回数を数えるだけです。

3. 実際の操作

10 億ファイルは大きすぎます。実際の操作は時間の無駄です。実用的な目的を達成するだけです。

問題のサイズは次のように削減されます: 1M メモリ制限、a と b にはそれぞれ 100,000 行のレコードがあります。メモリ制限は PHP の ini_set('memory_limit', '1M');# によって制限できます。 ##。

4. テスト ファイルの生成

ファイルを満たす乱数の生成:

/**
 * 生成随机数填充文件
 * 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 = &#39;&#39;;
        for ($j=0; $j<$batchSize; $j++) {
            $str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
        }
        file_put_contents($filename, $str, FILE_APPEND);  // 追加模式写入文件
    }
}

generate(&#39;a.txt&#39;, 10);
generate(&#39;b.txt&#39;, 10);

5. ファイルの分割

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');

splitFile 関数を実行すると、次の画像が得られます filesディレクトリ内に 20 個のファイル。

6. 重複レコードの検索

次に、20 個のファイルで同じレコードを検索する必要があります。実際には、1 つのファイルで同じレコードを検索する必要があります。ファイルを作成し、各 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のマルチコアを利用すれば1台のマシンでも対応できますが、足りない場合は複数のサーバーで対応することも可能です。

7. 完全なコード

ログイン後にコピー

(推奨チュートリアル:

PHP ビデオ チュートリアル )

以上がPHP が 2 つの大きなファイル内で同じレコードを検索する方法の詳細な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。