Une question d'entretien PHP que les grandes entreprises aiment poser !

PHP implémente un tri par fusion multidirectionnel simple de fichiers volumineux

C'est une question d'entretien courante, et certaines grandes entreprises aiment également utiliser cette question comme question d'entretien.

Question : Par exemple, il existe un fichier 1g, qui stocke ces nombres désordonnés et non uniques. Comment utiliser 100m pour effectuer le tri global ?

Le processus de mise en œuvre est  :

1. Lisez d'abord le gros fichier ligne par ligne, toutes les 10 000 lignes dans un groupe, puis triez-le et écrivez-le dans le fichier . txt, t2.txt... Un tel nom, jusqu'à ce que le fichier entier soit lu et divisé,

2 Ensuite, parcourez tous les fichiers, lisez d'abord la première ligne de chaque fichier, placez-le dans le tableau de tri temporaire $tmpNums*. *, puis prenez la valeur minimale, **Mettez-la dans le tableau de stockage temporaire $nums et enregistrez la valeur d'index de la position actuelle $idx

3 Prenez un numéro du fichier correspondant à l'index où se trouve la valeur minimale. est localisé, placez-le dans l'index actuel du tableau de tri temporaire, puis continuez à répéter la première. L'opération en 2 étapes est effectuée jusqu'à ce que tout le contenu de tous les fichiers soit lu, puis le fichier entier est réorganisé.

Ce qui suit est un code de démonstration de tri par fusion multidirectionnel PHP, qui n'est qu'une simple structure squelette. Par exemple, min prend la valeur minimale, qui peut être étendue en une implémentation de tas minimum de longueur fixe, ou une file d'attente prioritaire, qui peut enregistrer la valeur et le fichier dans lequel elle se trouve.

Code de démonstration de fusion multidirectionnelle PHP :

function multiWaySort()
{
    // 读取所有的文件描述符

    $fds = [];
    $dir = scandir('./runtime/txt/');
    foreach ($dir as $file) {
        if ($file != '.' && $file != '..') {
            $fds[] = fopen('./runtime/txt/' . $file, 'rb');
        }
    }

    // 读取每个文件的第一行内容，放入临时排序数组

    $tmpNums = [];
    foreach ($fds as $fd) {
        $tmpNums[] = (int)fgets($fd);
    }

    $nums = [];
    $count = 0;
    while (true) {
        if (empty($tmpNums)) break;

        // 最小值放入临时存储数组

        $value = min($tmpNums);
        $nums[] = $value;  

        // 读取最小值所在索引，对应的文件下一行内容

        $idx = array_search($value, $tmpNums);
        $next = fgets($fds[$idx]);

        if (!$next) {
            unset($tmpNums[$idx]);
            unset($fds[$idx]);
        } else {
            $tmpNums[$idx] = (int)$next;
        }

        // 临时存储数组到达一定数量追加写入文件一次

        if (count($nums) == 20) {
            foreach ($nums as $value) {
                $f = fopen('./runtime/result.txt', 'ab+');
                fwrite($f, $value . PHP_EOL);
            }
            $nums = [];
        }

        if ($count == 4999999) {
            continue;
        }

        $count++;
    }
}

Étude recommandée : "Tutoriel vidéo PHP"

Référence :

"Explication détaillée du tri de fusion K-way (combat réel)"

"Un article pour en savoir plus Problème de tri des fichiers/tri du stockage externe》

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!