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

题目:例如有一个 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++;
}
}

推荐学习:《PHP视频教程》

参考:

《详解K路归并排序(实战)》

《一文了解大文件排序/外存排序问题》

以上就是大厂喜欢出的一道PHP面试题!的详细内容,更多请关注811轩轩资源网其它相关文章!

声明:本文转载于:hxd.life,如有侵犯,请联系admin@php.cn删除

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注