关于php:PHP-实现简单多路归并排序大文件

41次阅读

共计 1145 个字符,预计需要花费 3 分钟才能阅读完成。

原文链接:何晓东 博客

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

题目:例如有一个 1g 的文件,外面寄存这乱序不惟一的数字,如果利用 100m 实现整体排序?

思路就是:先将大文件逐行读取,每 10000 行为一组,而后 排序后写入文件 中,文件名称相似 t1.txt, t2.txt … 这样的名称,直至读取和拆分结束整个文件,而后遍历所有文件,每个文件先读取第一行,放入长期排序数组 ,而后取其中最小值, 放入长期存储数组,同时记录索引地位,从对应文件中取下一个数字,放入以后索引中,而后持续反复这样的操作,直到所有文件的所有内容读取结束,长期排序数组也读取结束,则整体文件从新排序结束。

以下是一个 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. 实战 k 路归并排序

最初恰饭 阿里云全系列产品 / 短信包特惠购买 中小企业上云最佳抉择 阿里云外部优惠券

正文完
 0