Exemple détaillé de la façon dont PHP trouve les mêmes enregistrements dans deux gros fichiers

Cet article vous apporte des connaissances pertinentes sur PHP Étant donné deux fichiers a et b, avec respectivement x et y lignes de données (x et y sont tous deux supérieurs à 1 milliard), la limite de mémoire de la machine est de 100 Mo. Comment trouver. les mêmes enregistrements ? Cet article expliquera la méthode de mise en œuvre pour tout le monde. J'espère qu'il sera utile à tout le monde.

(Tutoriel recommandé : Tutoriel vidéo PHP)

1. Introduction

Étant donné deux fichiers a et b, avec respectivement x et y lignes de données, où (x, y sont tous deux supérieurs à 1 milliard) , La mémoire de la machine est limitée à 100 M, comment retrouver les mêmes enregistrements ?

2. Idée

• La principale difficulté pour résoudre ce problème est que ces données massives ne peuvent pas être lues dans la mémoire en une seule fois
• . ne peut pas être lu dans la mémoire en même temps, alors peut-il être considéré plusieurs fois ? Si c’est possible, comment pouvons-nous calculer la même valeur après l’avoir lue plusieurs fois ?
• Nous pouvons utiliser la pensée diviser pour mieux régner pour réduire le grand au petit. Si les valeurs d'une même chaîne sont égales après hachage, alors on peut envisager d'utiliser le hachage modulo pour disperser les enregistrements dans n fichiers. Comment obtenir ce n? PHP dispose de 100 Mo de mémoire et le tableau peut stocker environ 1 million de données. Ainsi, étant donné que les enregistrements a et b n'ont qu'un milliard de lignes, n doit être au moins supérieur à 200.
• Il y a actuellement 200 fichiers. Les mêmes enregistrements doivent être dans le même fichier, et chaque fichier peut être lu dans la mémoire. Ensuite, vous pouvez rechercher les mêmes enregistrements dans ces 200 fichiers dans l'ordre, puis les exporter dans le même fichier. Le résultat final est les mêmes enregistrements dans les deux fichiers a et b.
• Il est facile de trouver le même enregistrement dans un petit fichier. Utilisez simplement chaque ligne d'enregistrements comme clé de la table de hachage et comptez le nombre d'occurrences de la clé >= 2.

3. Opération pratique

1 milliard de fichiers sont trop gros et l'opération pratique est une perte de temps. Il suffit d'atteindre l'objectif pratique.

La taille du problème est réduite à : limite de mémoire de 1 M, a et b ont chacun 100 000 lignes d'enregistrements. La limite de mémoire peut être limitée par le ini_set('memory_limit', '1M'); de 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通过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

4. Générer un fichier de test

Générer des nombres aléatoires pour remplir le fichier :

/**
 * 查找一个文件中相同的记录输出到指定文件中
 * 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);
        }
    }
}

5. Divisez le fichier

Hash a.txt, b.txt Split. en n fichiers en utilisant la méthode modulo.

/**
 * 从给定目录下文件中分别找出相同记录输出到指定文件中
 * 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);
        }
    }
}

Exécutez la fonction splitFile et récupérez 20 fichiers dans le répertoire files comme indiqué ci-dessous.

6. Rechercher les enregistrements en double

Vous devez maintenant rechercher les mêmes enregistrements dans 20 fichiers. En fait, vous devez rechercher les mêmes enregistrements dans un seul fichier et opérer 20 fois.

Trouver les mêmes enregistrements dans un fichier :

Trouver les mêmes enregistrements dans tous les fichiers :🎜rrreee🎜Maintenant que le problème d'espace du traitement des fichiers volumineux a été résolu, comment gérer le problème de temps qu'une seule machine peut utiliser ? le multicœur du traitement CPU, sinon suffisant, via plusieurs serveurs. 🎜🎜7. Code complet🎜rrreee🎜 (tutoriel recommandé : 🎜Tutoriel vidéo PHP🎜)🎜
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!