A PHP interview question that big companies like to ask!

It is a common interview question, and some major companies also like to use this question as an interview question.

Question: For example, there is a 1g file, which stores these disordered and non-unique numbers. How to use 100m to complete the overall sorting?

The implementation process is:

1. First read the large file line by line, with every 10,000 lines in a group, and then write the file after sorting, the file name is similar to t1.txt, t2.txt... until the entire file is read and split,

2. Then traverse all files, and each file first reads the first In one line, is put into the temporary sorting array $tmpNums**, and then the minimum value is taken, ** is put into the temporary storage array $nums, and the index value of the current position is recorded at the same time $idx

The following is a PHP multi-way merge sort demo code, which is just a simple skeleton structure. For example, min takes the minimum value part, which can be expanded into a fixed-length minimum heap implementation, or a priority queue, which can save the value and the file where it is located. .

PHP multi-channel merge demo code:

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++;
    }
}

Recommended learning: "PHP Video Tutorial"

Reference :

《Detailed explanation of K-way merge sorting (actual combat)》

《One article to understand the problem of large file sorting/external memory sorting》