大厂喜欢出的一道PHP面试题！

145 阅读 0 评论 96 点赞

我是靠谱客的博主单身汉堡，这篇文章主要介绍大厂喜欢出的一道PHP面试题！，现在分享给大家，希望可以做个参考。

算是一道常见的面试题引来的，有些大厂也喜欢把这个题当做面试题。

题目：例如有一个 1g 的文件，里面存放这乱序不唯一的数字，如果利用 100m 完成整体排序？

实现过程就是：

1、先将大文件逐行读取，每 10000 行为一组，然后排序后写入文件中，文件名称类似 t1.txt, t2.txt ... 这样的名称，直至读取和拆分完毕整个文件，

2、然后遍历所有文件，每个文件先读取第一行，放入临时排序数组 $tmpNums**，然后取其中最小值，**放入临时存储数组 $nums，同时记录当前位置的索引值 $idx

3、从最小值所在索引对应文件中取下一个数字，放入临时排序数组的当前索引中，然后继续重复第 2 步的操作，直到所有文件的所有内容读取完毕，则整体文件重新排序完毕。

以下是一个 PHP 多路归并排序 demo 代码，只是简单的骨架结构，例如 min 取最小值部分，可以扩展成定长最小堆实现，或者优先队列，能保存值和所在文件就行。

PHP 多路归并 demo 代码：

复制代码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++;
    }
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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++;
    }
}
登录后复制