作为一名主要的 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
真的没有使用快速排序的实现吗?是不是因为我没有考虑数组键(在我的情况下我不需要键/值对保持不变)?以防万一有人想要在 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;
}
}
}
最佳答案
考虑传递给 QuickSort
的参数和传递给 usort()
的参数之间的区别。 usort()
有一个更通用的接口(interface),它根据比较函数进行操作。您的 QuickSort
专门用于您的特定类型的数据,并通过 >
运算符执行比较。
那么,性能差异很可能是由于评估函数调用相对于评估单个 >
操作的成本要高得多。这种差异很容易抵消 usort()
可能具有的任何固有的效率优势。此外,由于它依赖于用 PHP 编写的比较函数,因此 usort()
的操作涉及运行大量 PHP,而不仅仅是编译的 C 代码。
如果您想进一步探索这一点,请考虑修改您的实现以呈现与 usort()
相同的接口(interface)。我倾向于猜测 usort()
会通过这种手卷变体赢得苹果对苹果的比较,但众所周知,性能很难预测。这就是我们测试的原因。