为什么自我实现的快速排序比内部快速排序更快？

Question

作为一名主要 PHP 开发人员（并且自学成才），我从来没有真正有理由去了解或理解诸如排序算法之类的算法背后的算法，除了快速排序平均而言是最快的，并且它通常是 PHP 排序函数背后的算法。

但我有一个待定的面试即将到来，他们建议了解像这样的基本算法。所以我打开 http://www.geeksforgeeks.org/quick-sort/ 并实现了我自己的 QuickSort 和 Partition 函数，当然是为了练习，用于按其中一个值对数组进行排序。我想到了这个（我使用的是 PHP 7.1，所以相当一部分语法相对较新）

function Partition(array &$Array, $Column, int $Low, int $High): int {
    $Pivot = $Array[$High][$Column];

    $i = $Low - 1;

    for ($j = $Low; $j <= $High - 1; $j++) {
        if ($Array[$j][$Column] > $Pivot) {
            $i++;
            [$Array[$i], $Array[$j]] = [$Array[$j], $Array[$i]];
        }
    }

    [$Array[$i + 1], $Array[$High]] = [$Array[$High], $Array[$i + 1]];
    return $i + 1;
}

function QuickSort(array &$Array, $Column, int $Low = 0, ?int $High = null): void {
    $High = $High ?? (count($Array) - 1);

    if ($Low < $High) {
        $PartitionIndex = Partition($Array, $Column, $Low, $High);

        QuickSort($Array, $Column, $Low, $PartitionIndex - 1);
        QuickSort($Array, $Column, $PartitionIndex + 1, $High);
    }
}

而且有效！惊人的！所以我想，使用它没有实际意义，因为这个算法的 PHP 解释版本不可能比编译的 C 版本更快（就像在 usort 中使用的那样）。但不管怎样，我决定对这两种方法进行基准测试。

令我惊讶的是，我的速度更快！

$Tries = 1000;
$_Actions = $Actions;

$Start = microtime(true);
for ($i = 0; $i < $Tries; $i++) {
    $Actions = $_Actions;
    usort($Actions, function($a, $b) {
        return $b['Timestamp'] <=> $a['Timestamp'];
    });
}
echo microtime(true) - $Start, "\n";

$Start = microtime(true);
for ($i = 0; $i < $Tries; $i++) {
    $Actions = $_Actions;
    QuickSort($Actions, 'Timestamp');
}
echo microtime(true) - $Start, "\n";

这为我提供了第一个 1.274071931839 和第二个 0.87327885627747 左右的一致数字。

有没有我遗漏的愚蠢的东西会导致这种情况？ usort 真的没有使用快速排序的实现吗？是不是因为我没有考虑数组键（在我的例子中，我不需要 key/value 对保持不变）？

以防万一有人想要 PHP 中完成的 QuickSort 函数，这就是我最终得到的结果，它按列降序对数组进行排序，大约是原生 usort 的一半时间. （迭代，不是递归，分区函数也是内联的）

function array_column_sort_QuickSort_desc(array &$Array, $Column, int $Start = 0, int $End = null): void {
    $End = $End ?? (count($Array) - 1);

    $Stack = [];
    $Top = 0;

    $Stack[$Top++] = $Start;
    $Stack[$Top++] = $End;

    while ($Top > 0) {
        $End = $Stack[--$Top];
        $Start = $Stack[--$Top];

        if ($Start < $End) {
            $Pivot = $Array[$End][$Column];

            $PartitionIndex = $Start;

            for ($i = $Start; $i < $End; $i++) {
                if ($Array[$i][$Column] >= $Pivot) {
                    [$Array[$i], $Array[$PartitionIndex]] = [$Array[$PartitionIndex], $Array[$i]];
                    $PartitionIndex++;
                }
            }

            [$Array[$End], $Array[$PartitionIndex]] = [$Array[$PartitionIndex], $Array[$End]];

            $Stack[$Top++] = $Start;
            $Stack[$Top++] = $PartitionIndex - 1;

            $Stack[$Top++] = $PartitionIndex + 1;
            $Stack[$Top++] = $End;
        }
    }
}

Answer 1

考虑传递给 QuickSort 的参数与传递给 usort() 的参数之间的区别。 usort() 有一个更通用的接口，它根据比较功能运行。您的 QuickSort 专用于特定类型的数据，并通过 > 运算符进行比较。

那么，性能差异很可能归因于评估函数调用相对于评估单个 > 操作的成本要高得多。这种差异很容易淹没 usort() 可能具有的任何固有效率优势。此外，考虑到因为它依赖于 PHP 中编写的比较函数，usort() 的操作涉及运行很多 PHP，而不仅仅是编译的 C 代码。

如果您想进一步探索这一点，请考虑修改您的实现以呈现与 usort() 相同的界面。我倾向于猜测 usort() 会在与这种手动变体的同类比较中胜出，但性能是出了名的难以预测。这就是我们测试的原因。

为什么自我实现的快速排序比内部快速排序更快？

Why is self-implemented quicksort faster than internal quicksort?

php

big-o

quicksort