实现稳定排序

在设计数组排序逻辑时，最初的 PHP 开发人员牺牲了稳定性来换取速度。在当时看来，这种牺牲是合理的。但是，如果在排序过程中涉及复杂对象，就需要 稳定的排序。

在本节中，我们将讨论什么是稳定排序，以及为什么它很重要。如果能确保数据的稳定排序，您的应用代码就能产生更准确的输出，从而提高客户满意度。在详细介绍 PHP 8 如何实现稳定排序之前，我们首先需要定义什么是稳定排序。

了解稳定排序

当用于排序的属性值相等时，在稳定排序中就能保证元素的原始顺序。这样的结果更接近用户的期望。让我们来看一个简单的数据集，并确定稳定排序的构成要素。为了便于说明，假设我们的数据集包含访问时间和用户名条目：

2021-06-01 11:11:11 Betty
2021-06-03 03:33:33 Betty
2021-06-01 11:11:11 Barney
2021-06-02 02:22:22 Wilma
2021-06-01 11:11:11 Wilma
2021-06-03 03:33:33 Barney
2021-06-01 11:11:11 Fred

如果我们想按时间排序，您会立即注意到 2021-06-01 11:11:11 有重复。如果我们对这个数据集进行稳定排序，预期结果如下：

2021-06-01 11:11:11 Betty
2021-06-01 11:11:11 Barney
2021-06-01 11:11:11 Wilma
2021-06-01 11:11:11 Fred
2021-06-02 02:22:22 Wilma
2021-06-03 03:33:33 Betty
2021-06-03 03:33:33 Barney

从排序后的数据集中可以看到，重复时间 2021-06-01 11:11:11 的条目是按照最初输入的顺序出现的。因此，我们可以说这个结果代表了一种稳定的排序。

在理想情况下，同样的原则也应适用于保留键/值关联的排序。稳定排序的另一个标准是，它的性能应与无规范排序无异。

有关 PHP 8 稳定版的更多信息，请点击此处查看官方 RFC： https://wiki.php.net/rfc/stable_sorting 。

在 PHP 8 中，重写了核心 *sort*() 函数和 ArrayObject::*sort*() 方法，以实现稳定的排序。下面我们来看一个代码示例，以说明在 PHP 早期版本中可能出现的问题。

稳定排序与非稳定排序对比

在本例中，我们希望按时间对 Access 实例数组进行排序。每个 Access 实例都有两个属性：$name 和 $time。示例数据集包含重复的访问时间，但用户名不同：

  1. 首先，我们定义 Access 类：

    // /repo/src/Php8/Sort/Access.php
namespace Php8\Sort;
class Access {
    public $name, $time;
    public function __construct($name, $time) {
        $this->name = $name;
        $this->time = $time;
    }
}

  2. 接下来，我们定义一个样本数据集，它由 CSV 文件 /repo/sample_data/access.csv 组成，共有 21 行。每一行代表不同的名称和访问时间组合：

    "Fred", "2021-06-01 11:11:11"
"Fred", "2021-06-01 02:22:22"
"Betty", "2021-06-03 03:33:33"
"Fred", "2021-06-11 11:11:11"
"Barney","2021-06-03 03:33:33"
"Betty", "2021-06-01 11:11:11"
"Betty", "2021-06-11 11:11:11"
"Barney","2021-06-01 11:11:11"
"Fred", "2021-06-11 02:22:22"
"Wilma", "2021-06-01 11:11:11"
"Betty", "2021-06-13 03:33:33"
"Fred", "2021-06-21 11:11:11"
"Betty", "2021-06-21 11:11:11"
"Barney","2021-06-13 03:33:33"
"Betty", "2021-06-23 03:33:33"
"Barney","2021-06-11 11:11:11"
"Barney","2021-06-21 11:11:11"
"Fred", "2021-06-21 02:22:22"
"Barney","2021-06-23 03:33:33"
"Wilma", "2021-06-21 11:11:11"
"Wilma", "2021-06-11 11:11:11"

    在扫描样本数据时，您会注意到所有输入时间为 11:11:11 的日期都是重复的，但是，您也会注意到任何给定日期的原始顺序总是用户 Fred、Betty、Barney 和 Wilma。此外，请注意，对于时间为 03:33:33 的日期，贝蒂的条目总是排在巴尼之前。

  3. 然后我们定义一个调用程序。在这个程序中，首先要做的是配置自动加载并使用 Access 类：

    // /repo/ch010/php8_sort_stable_simple.php
require __DIR__ . '/../src/Server/Autoload/Loader.php';
$loader = new \Server\Autoload\Loader();
use Php8\Sort\Access;

  4. 接下来，我们将样本数据加载到 $access 数组中：

    $access = [];
$data = new SplFileObject(__DIR__ . '/../sample_data/access.csv');
while ($row = $data->fgetcsv())
    if (!empty($row) && count($row) === 2)
        $access[] = new Access($row[0], $row[1]);

  5. 然后执行 usort()。请注意，用户定义的回调函数会对每个实例的时间属性进行比较：

    usort($access, function($a, $b) { return $a->time <=> $b->time; });

  6. 最后，我们循环遍历新排序的数组并显示结果：

    foreach ($access as $entry)
    echo $entry->time . "\t" . $entry->name . "\n";

在 PHP 7 中，请注意虽然时间是按顺序排列的，但名称并不反映预期的顺序 Fred、Betty、Barney 和 Wilma。下面是 PHP 7 的输出结果：

root@php8_tips_php7 [ /repo/ch10 ]#
php php8_sort_stable_simple.php
2021-06-01 02:22:22 Fred
2021-06-01 11:11:11 Fred
2021-06-01 11:11:11 Wilma
2021-06-01 11:11:11 Betty
2021-06-01 11:11:11 Barney
2021-06-03 03:33:33 Betty
2021-06-03 03:33:33 Barney
2021-06-11 02:22:22 Fred
2021-06-11 11:11:11 Barney
2021-06-11 11:11:11 Wilma
2021-06-11 11:11:11 Betty
2021-06-11 11:11:11 Fred
2021-06-13 03:33:33 Barney
2021-06-13 03:33:33 Betty
2021-06-21 02:22:22 Fred
2021-06-21 11:11:11 Fred
2021-06-21 11:11:11 Betty
2021-06-21 11:11:11 Barney
2021-06-21 11:11:11 Wilma
2021-06-23 03:33:33 Betty
2021-06-23 03:33:33 Barney

从输出结果中可以看到，在第一组 11:11:11 的日期中，最终顺序是 Fred、Wilma、Betty 和 Barney，而最初的输入顺序是 Fred、Betty、Barney 和 Wilma。您还会注意到，在日期和时间 2021-06-13 03:33:33 中，Barney 排在 Betty 之前，而原来的输入顺序正好相反。根据我们的定义，PHP 7 没有实现稳定排序！

现在让我们看一下在 PHP 8 中运行的相同代码示例。以下是 PHP 8 输出：

root@php8_tips_php8 [ /repo/ch10 ]#
php php8_sort_stable_simple.php
2021-06-01 02:22:22 Fred
2021-06-01 11:11:11 Fred
2021-06-01 11:11:11 Betty
2021-06-01 11:11:11 Barney
2021-06-01 11:11:11 Wilma
2021-06-03 03:33:33 Betty
2021-06-03 03:33:33 Barney
2021-06-11 02:22:22 Fred
2021-06-11 11:11:11 Fred
2021-06-11 11:11:11 Betty
2021-06-11 11:11:11 Barney
2021-06-11 11:11:11 Wilma
2021-06-13 03:33:33 Betty
2021-06-13 03:33:33 Barney
2021-06-21 02:22:22 Fred
2021-06-21 11:11:11 Fred
2021-06-21 11:11:11 Betty
2021-06-21 11:11:11 Barney
2021-06-21 11:11:11 Wilma
2021-06-23 03:33:33 Betty
2021-06-23 03:33:33 Barney

从 PHP 8 的输出中可以看到，在所有 11:11:11 的条目中，Fred、Betty、Barney 和 Wilma 的原始条目顺序都得到了遵守。您还会注意到，在日期和时间 2021-06-13 03:33:33 中，Betty 一直排在 Barney 之前。因此，我们可以得出结论：PHP 8 执行了稳定的排序。

现在您已经看到了 PHP 7 中的问题，并且知道 PHP 8 解决了这个问题，让我们看看稳定排序对键的影响。

检查稳定排序对键的影响

在使用 asort()、uasort() 或等效 ArrayIterator 方法时，稳定排序的概念也会影响键/值对。在下一个示例中，ArrayIterator 中填充了 20 个元素，每个元素都是重复的。键是一个按顺序递增的十六进制数：

  1. 首先，我们定义了一个生成随机 3 个字母组合的函数：

    // /repo/ch010/php8_sort_stable_keys.php
$randVal = function () {
    $alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    return $alpha[rand(0,25)] . $alpha[rand(0,25)]
        . $alpha[rand(0,25)];};

  2. 接下来，我们载入一个带有样本数据的 ArrayIterator 实例。每个其他元素都是重复的。我们还捕获了起始时间：

    $start = microtime(TRUE);
$max = 20;
$iter = new ArrayIterator;
for ($x = 256; $x < $max + 256; $x += 2) {
    $key = sprintf('%04X', $x);
    $iter->offsetSet($key, $randVal());
    $key = sprintf('%04X', $x + 1);
    $iter->offsetSet($key, 'AAA'); // <-- duplicate
}

  3. 然后，我们执行 ArrayIterator::asort() 并显示结果顺序和所用时间：

    // not all code is shown
$iter->asort();
foreach ($iter as $key => $value) echo
"$key\t$value\n";
echo "\nElapsed Time: " . (microtime(TRUE) - $start);

下面是该代码示例在 PHP 7 中运行的结果：

root@php8_tips_php7 [ /repo/ch10 ]#
php php8_sort_stable_keys.php
0113 AAA
010D AAA
0103 AAA
0105 AAA
0111 AAA
0107 AAA
010F AAA
0109 AAA
0101 AAA
010B AAA
0104 CBC
... some output omitted ...
010C ZJW
Elapsed Time: 0.00017094612121582

从输出结果中可以看出，虽然值是按顺序排列的，但在值重复的情况下，键的顺序会出现混乱。相比之下，请看在 PHP 8 中运行的相同程序代码的输出结果：

root@php8_tips_php8 [ /repo/ch10 ]#
php php8_sort_stable_keys.php
0101 AAA
0103 AAA
0105 AAA
0107 AAA
0109 AAA
010B AAA
010D AAA
010F AAA
0111 AAA
0113 AAA
0100 BAU
... some output omitted ...
0104 QEE
Elapsed Time: 0.00010395050048828

输出结果表明，任何重复条目的键都会按原来的顺序出现在输出结果中。输出结果表明 PHP 8 不仅对值而且对键都实现了稳定的排序。此外，正如耗时结果所显示的，PHP 8 成功地保持了与以前相同（或更好）的性能。现在让我们来看看 PHP 8 中直接影响数组排序的另一个不同之处：对非法排序功能的处理。

处理非法排序函数

PHP 7 和更早版本允许开发人员在使用 usort() 或 uasort()（或等效的 ArrayIterator 方法）时使用 非法函数。意识到这种不良做法是非常重要的。否则，当您将代码移植到 PHP 8 时，就会出现潜在的向后兼容性问题。

在下一个示例中，创建的数组与 "稳定排序与非稳定排序的对比" 一节中描述的示例相同。非法排序功能返回一个布尔值，而 u*sort() 回调需要返回两个元素之间的相对位置。从字面上看，如果第一个操作数小于第二个操作数，用户定义的函数或回调函数需要返回-1；如果相等，则返回 0；如果第一个操作数大于第二个操作数，则返回 1。如果我们重写定义 usort() 回调的代码行，一个非法函数可能会如下所示：

usort($access, function($a, $b) {
    return $a->time < $b->time; });

在此代码片段中，我们没有使用空格运算符 (<=>)（空格运算符会返回-1、0 或 1），而是使用了小于符号 (<)。在 PHP 7 及以下版本中，返回布尔值的回调是可以接受的，并能产生所需的结果。但实际情况是，PHP 解释器需要添加额外的操作来弥补缺少的操作。因此，如果回调只执行以下比较操作：

op1 > op2

PHP 解释器增加了一个额外的操作：

op1 <= op2

在 PHP 8 中，非法的排序功能会产生一个弃用通知。下面是在 PHP 8 中运行的重写代码：

root@php8_tips_php8 [ /repo/ch10 ]#
php php8_sort_illegal_func.php
PHP Deprecated: usort(): Returning bool from comparison
function is deprecated, return an integer less than, equal to,
or greater than zero in /repo/ch10/php8_sort_illegal_func.php
on line 30
2021-06-01 02:22:22 Fred
2021-06-01 11:11:11 Fred
2021-06-01 11:11:11 Betty
2021-06-01 11:11:11 Barney
... not all output is shown

从输出结果中可以看到，PHP 8 允许操作继续进行，并且在使用适当的回调时结果是一致的。不过，我们也可以看到 PHP 8 发布了一个 "报废通知"。

您还可以使用 PHP 8 中的箭头函数。前面显示的回调可能会重写如下：

usort($array, fn($a, $b) => $a <=> $b).

现在，您对什么是稳定排序以及它的重要性有了更深入的了解。您还能发现由于 PHP 8 与早期版本在处理上的差异而导致的潜在问题。现在我们来看看 PHP 8 中引入的其他性能改进。