Почему самореализованная быстрая сортировка быстрее, чем внутренняя быстрая сортировка?

Будучи в основном разработчиком 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 не реально использовать реализацию быстрой сортировки? Это потому, что я не принимаю во внимание ключи массива (в моем случае мне не нужны пары ключ / значение, чтобы они оставались неизменными)?


На всякий случай, если кто-то захочет получить готовую функцию QuickSort в PHP, это то, чем я закончил, который сортирует массивы по столбцам по убыванию, примерно вдвое быстрее, чем нативные. 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;
}
}
}

4

Решение

Рассмотрите разницу между аргументами, которые вы передаете QuickSort и те, которые вы передаете usort(), usort() имеет гораздо более общий интерфейс, который работает с точки зрения функции сравнения. Ваш QuickSort специализируется для вашего конкретного типа данных и для проведения сравнений с помощью > оператор.

Таким образом, весьма вероятно, что разница в производительности объясняется гораздо более высокой стоимостью оценки вызовов функций по сравнению с оценкой отдельных > операции. Это различие может легко затмить любое преимущество в эффективности, которое usort() должно быть. Кроме того, учтите, что поскольку он опирается на функцию сравнения, написанную на PHP, usort()Операция включает в себя запуск большого количества PHP, а не только скомпилированного кода на языке Си.

Если вы хотите изучить это дальше, подумайте о том, чтобы изменить свою реализацию, чтобы представить тот же интерфейс, который usort() делает. Я был бы склонен предположить, что usort() выиграет сравнение яблок с яблоками с таким изменением, но общеизвестно, что производительность трудно предсказать. Вот почему мы тестируем.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]