PHP 版外部排序算法实现代码

一些排序算法如： 冒泡排序 、 选择排序 ❙、 、 快速排序, 堆排序 。 （建议朋友们掌握这些最基本的排序算法，并记得随时记下来）

但并不是所有人都听说过外部排序。作为学生，他们写的项目大部分都是玩具，所以很少有大量的数据需要处理，所以没有必要使用外部排序。

但是从今天开始，小伙伴们一定要知道什么是外部排序了。

没错。通常，需要排序的数据量很小，所以我们可以通过编写快速排序等排序算法来对数据进行排序。而所有这些排序算法都有一个属性：只使用内存，所以这些算法被称为内部排序。而外部排序则使用磁盘等外部存储器来进行排序过程。为什么需要使用外部存储？因为要排序的数据量非常大，比如几十G，但可用内存只有几G。因此，我们不能直接使用内部排序，必须使用外部内存来完成整个排序过程。

外部排序的一般认识

1.循环从整个大文件中读取一定量的数据到内存中，然后将这部分数据排序后写入到小文件中。达到将整个大文件分割成一定数量的小文件的目的。

2。由于每个小文件中的数据都是排序的，因此可以将小文件合并，最终得到完全排序的大文件。

开始

首先我们定义一些接口和类，以便更轻松地读写文件。

FileInterface.php 文件：

interface FileInterface
{
	public function read();
	public function write($file);
}

SortingAlgorithmInterface.php 文件：

<?php

interface SortingAlgorithmInterface
{
	public function sort($outputPath);
}

File.php 文件：

<?php

class File implements FileInterface
{

	public $file;
	public $list = [];
	public $fileSize;
	
	function __construct($file)
	{
		$this->file = $file;
		$this->fileSize = filesize($file); // 得到文件大小
	}

	public function read($offset= 0, $maxlen = 500000 )
	{
		// 将整个文件读入一个字符串
		$list = file_get_contents($this->file);
		$this->list = explode(',', $list); // 将字符串打散为数组
		$list = null;
	}

	public function write($file)
	{
		// 打开文件$file，如果不存在则创建它
		$file = fopen($file, 'w');
        // 把排好序的数组合并成字符串后写入文件
		$string = fwrite($file, implode("\n", $this->list) );
		fclose($file);
	}
}

我在这里提到一件事，write❙ implode( "\n", $ this- >list)，即"\n"用于组合表的元素并将其写入文件。使用 "\n" 的原因是为了更容易从文件中读取值。

OK，现在来解释一下关键函数，也就是ModifiedMergeSort.php文件的内容。

我们先看看ModifiedMergeSort类的成员变量：

class ModifiedMergeSort implements SortingAlgorithmInterface {
    protected $file;
	protected $sizeLimit;
	protected $tmpFiles = [];
}

$file用来存储文件对象，它是一个

$sizeLimit 用于存储我们可以使用多少内存来执行排序的值。

$tmpFiles用于保存小文件的文件名。 ？我们使用的内存大小采用外部排序，即调用externalSort方法；否则，将整个文件读入内存，然后直接在内存中执行内部排序。

让我们重点关注外部排序方法。

protected function externalSort() 
	{
		// 分成小块
		$this->chunk();
		// 文件拆分后，将它们按正确的顺序重新组合在一起
		$this->mergeFile();

		echo "External sort TBC\n";
	}

如你所见，这就是我们上面写的外层排序的总体思路：先分块，然后合并。

好吧，我们来看看如何将一个大文件拆分成几个小文件：

protected function chunk()
	{
		echo "Splitting file...\n";

		$handle = fopen($this->file->file, "r") or die("Couldn't get handle");

		if ($handle) {

			$tmpNum = 1;

            // 检测文件指针是否已到达文件末尾
		    while (!feof($handle)) {
		        $buffer = fgets($handle, $this->sizeLimit);

		        $list = explode(',', $buffer);

		        // 在把数据保存在临时文件之前排序
		        // $list数组里面是已经排好序的了
		        sort($list);

		        // 移除空域
		        $this->file->list = array_filter($list);

		        $fileName = 'tmp-' . $tmpNum . '.txt';

		        $this->file->write("output/$fileName");

		        $this->tmpFiles[] = $fileName;

		        ++$tmpNum;

                // fstat() 函数返回关于打开文件的信息，fstat($handle)['size']是文件大小
		        // $this->tmpFiles[$fileName]['size'] = fstat($handle)['size'];

		        echo "New file: output/$fileName\n";
		    }

		    fclose($handle);
		}
	}

重点关注while循环的内容。

$buffer = fgets($handle, $this->sizeLimit);

换句话说，我们每次通过循环读取 sizeLimit 字节的数据。

$list = explode(',', $buffer);

换句话说，我们将这些数据的字符串转换为数组。

sort($list);

换句话说，将这个矩阵从小到大排序。

$fileName = 'tmp-' . $tmpNum . '.txt';
$this->file->write("output/$fileName");

也就是说，将排序后的数据写入一个小文件中。小文件的命名格式为tmp-小文件数量-.txt。

OK，文件共享完成，下一步就是合并。

protected function mergeFile() {
    echo "正在归并...\n";

    // 判断归并是否结束
    $flag_num = 0;
    // 最小数字的文件索引
    $min_data_index = -1;
    // 最小数字
    $min_data = PHP_INT_MAX;

    $little_file_nums = count($this->tmpFiles);

    // 用来存放所有小文件的文件句柄
    $handle = [];

    // 用来存放大文件的文件句柄
    $big_file_handle = fopen('output/big_file.txt', 'w');
    // 用来存放小文件的第一个数字，即该文件的最小值
    $first_data = [];

    for ($i = 0; $i < $little_file_nums; ++$i) {
        $handle[$i] = fopen('output/' . $this->tmpFiles[$i], "r");
    }

    for ($i = 0; $i < $little_file_nums; ++$i) {
        $first_data[$i] = (int)fgets($handle[$i]);

        if ($min_data > $first_data[$i]) {
            $min_data_index = $i;
            $min_data = $first_data[$i];
        }
    }

    fwrite($big_file_handle, $min_data);
    fwrite($big_file_handle, "\n");

    while (1) { // 文件全部读取完毕
        $first_data[$min_data_index] = (int)fgets($handle[$min_data_index]);
        if ($first_data[$min_data_index] == false) {
            ++$flag_num;
            $first_data[$min_data_index] = PHP_INT_MAX;

            if ($flag_num == $little_file_nums) {
                break;
            }
        }

        $min_data_index = -1;
        $min_data = PHP_INT_MAX;

        // 找出数组中最小的数字
        for ($i = 0; $i < $little_file_nums; ++$i) {
            if ($min_data > $first_data[$i]) {
                $min_data_index = $i;
                $min_data = $first_data[$i];
            }
        }

        fwrite($big_file_handle, $min_data);
        fwrite($big_file_handle, "\n");
    }

    for ($i = 0; $i < $little_file_nums; ++$i) {
        fclose($handle[$i]);
    }
}

这里我们使用多路归并排序而不是双向归并排序。

多路归并排序思想：

• 在每个小文件中，读取文件指针指向的数字（因为是有序的，所以是文件的最小数字），存入first_data表中;
• 查找查找first_data表min_data及其对应文件索引中最小的编号；
• 将first_data表中找到的最小数字写入大文件big_file.txt，然后更新表first_data（根据索引而不是min_data读取文件的下一个数字）；
• 判断所有小文件中的数据是否全部读取完毕。如果没有，请继续连接。如果所有内容都被读取，则跳出循环并停止合并。

于是你得到如下流程图：

这些步骤中比较困难的部分是如何判断所有数据已被读取。最愚蠢的方法之一是每次循环时评估所有文件的文件指针是否都指向 EOF。如果都显示EOF，则表示数据已全部读取。完全的;否则不行，你需要继续阅读。然而，在这种情况下，每次都必须检查所有文件指针。如果有几万个小文件的话，需要花费很多时间，所以我没有使用这种方式。

所以我问了一位正在计划法语比赛的室友，我得到了一个想法：既然我们知道有多少个小文件，我们就可以计算总共有多少个文件指针到达了文件的末尾。 。当到达文件末尾的文件指针的数量等于小文件的数量时，我们就可以断定数据已经全部读取完毕，也就是下面的代码：

if ($flag_num == $little_file_nums) {
    break;
}

OK，我来详细说明一下数量：

$first_data[$i] = (int)fgets($handle[$i]);

这里，对从文件中读取的数据进行数据类型转换。原因是：从文件中读取的数字是字符串类型，而字符串类型在大小比较上存在一些缺陷。例如，字符串 "123" 小于字符串 "5"。

这是我的测试数据：

（我正在排序大约46MB的数据，内存限制为1MB）

看起来大约需要185秒，也就是3分钟左右。

好了，外部排序就这样了。其实还有很大的优化空间，特别是在合并过程中，可以利用winner trees和loser trees进行优化。当我有时间时我会添加更多。

获取源码

作者：黄瀚涛
链接：https://juejin.im/post/5acdf4bc6fb9a028d93784e8s来源：❙作者。商业转载请联系作者获得许可。非商业转载请注明出处。