作为一个主要是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.

我有什么愚蠢的东西会导致这种情况吗？是不是真的使用了quicksort的实现？是因为我没有考虑数组键(在我的情况下,我不需要键/值对保持不变)？

以防万一有人想在PHP中完成QuickSort函数,这就是我最终得到的结果,它按列排序,降序,大约一半的时间是本机的. (迭代,不是递归,分区函数也是内联的)

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;
        }
    }
}

解决方法:

考虑传递给QuickSort的参数与传递给usort()的参数之间的区别. usort()有一个更通用的接口,它在比较函数方面运行.您的QuickSort专门用于您的特定数据类型,并通过>进行比较.操作符.

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

如果您想进一步探讨这一点,请考虑修改您的实现以呈现usort()所做的相同接口.我倾向于猜测usort()会赢得与这种手动变化的苹果对苹果的比较,但很难预测性能.这就是我们测试的原因.