У меня есть пример usort (), и я добавил несколько выражений эха, чтобы увидеть, как работает код:
<?php function list_cmp($a, $b) { global $order; echo "\$a=$a, \$b=$b </br>"; foreach ($order as $key => $value) { echo "\$value=$value </br>"; if ($a == $value) { echo "\$a=\$value, returing 0. </br>"; return 0; } if ($b == $value) { echo "\$b=\$value, returing 1. </br>"; return 1; } } } $order[0] = 1; $order[1] = 3; $order[2] = 4; $order[3] = 2; $array[0] = 2; $array[1] = 1; $array[2] = 3; $array[3] = 4; $array[4] = 2; array[5] = 1; $array[6] = 2; usort($array, "list_cmp"); ?> Выходной код этого кода:
$a=2, $b=1 $value=1 $b=$value, returing 1. $a=2, $b=3 $value=1 $value=3 $b=$value, returing 1. $a=1, $b=3 $value=1 $a=$value, returing 0. $a=2, $b=4 $value=1 $value=3 $value=4 $b=$value, returing 1. $a=3, $b=4 $value=1 $value=3 $a=$value, returing 0. $a=2, $b=2 $value=1 $value=3 $value=4 $value=2 $a=$value, returing 0. $a=2, $b=1 $value=1 $b=$value, returing 1. $a=2, $b=1 $value=1 $b=$value, returing 1. $a=4, $b=1 $value=1 $b=$value, returing 1. $a=3, $b=1 $value=1 $b=$value, returing 1. $a=1, $b=1 $value=1 $a=$value, returing 0. $a=2, $b=2 $value=1 $value=3 $value=4 $value=2 $a=$value, returing 0.
Каков механизм создания пар 12 $ a- $ b – 2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1 (опять же ?), 4-1, 3-1, 1-1, 2-2. Вышеупомянутый код возвращает 1,1,0,1,0,0,1,1,1,1,0,0. А также каков механизм сортировки массива, основанный на возвращаемых значениях? Я пытаюсь понять, как работает механизм usort ().
Благодарю.
Я не уверен, что это было частью вопроса, но чтобы было ясно, как работает компаратор: у вас есть заказ, заданный упорядоченным списком $order и специальным обратным list_cmp который должен (должен) возвращать более аргумент
$a меньше, чем $b ( return -1 или значение < 0 ) $a больше $b ( return 1 или value > 0 ) $a равный $b ( return 0 ) list_cmp делает это, просматривая свою таблицу заказов и скорее проверяя, если
$a имеет меньший (или равный) порядок, в этом случае цикл выходит с раннего return 0 или if $b имеет меньший порядок, и в этом случае цикл выходит с раннего return 1 . Имейте в виду, что это неверно в соответствии с документацией PHP, в которой говорится, что он хочет получить положительные / отрицательные значения / 0 в качестве возвращаемых значений. Это справедливо только в том случае, если вы знаете, что внутренности проверяют только для comparator($a,$b) > 0 , что означает, что он проверяет, меньше ли $b и не равен $a , что делает этот order of $a <= order of $b сравнения order of $a <= order of $b . Он может легко сломаться, если код начинает проверять, что значение $a меньше и не равно $b .
Для начала я предполагаю, что вы используете PHP 7 или выше. В этом случае вы попадаете в специальный корпус с массивами размером 6-15 элементов. PHP 7+, похоже, не использует quicksort для коротких списков, вместо этого он использует вариант сортировки вставки (который, скорее всего, быстрее из-за связанных с оборудованием материалов, таких как локализация кэширования / кода). Вы можете проверить исходный код сортировки fe на Github PHP Mirror (в качестве примера: PHP 7.0 Zend / Zend_sort.c Линия 177-198) .
Код работает в 3 этапа:
array[j] и array[j+1] , если array[j] <= array[j+1] переместится, else goto 2. array[j] > array[j+1] , отсканируйте назад, чтобы найти точку, где array[x] < array[j+1] <= array[x+1] для x < j (очевидно только до тех пор, пока x запустится) x+1 ... j один вверх так, чтобы он становился x+2 ... j+1 и вставлял прежний элемент в положение x+1 Если вы применяете этот код к парам (2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1, 4-1, 3-1, 1 -1, 2-2) становится очевидным, что делает код.
-- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2 -- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2) -- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2 -- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2) -- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2 -- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip -- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1 -- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1 -- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1 -- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1 -- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3 -- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip -- sorted: 1,1,3,4,2,2,2
PS: Здесь вы уже видите, что довольно сложно получить работу даже простого алгоритма сортировки (22 строки кода) по шаблонам сравнения. Реализация быстрых пользователей PHP 7 примерно в 10 раз больше по строкам кода и имеет некоторые причудливые оптимизации (помимо обычного безумия из-за выбора и рекурсий).
В большинстве случаев лучше игнорировать подробные детали реализации и сводить их только к тому, что необходимо. Типичными вопросами для алгоритма сортировки были бы, если они стабильны / неустойчивы и выполняются в O(log n) с O(n) потреблением памяти. Есть более простые способы изучить основные алгоритмы для этих оптимизированных реализаций, таких как Quicksort Dance или любую другую визуализацию, или добрую старую (e) книгу или веб-страницу с примерами.
– Отредактировано
Добавлена (плохая, неоптимизированная, небезопасная) реализация php для сортировки вставки для другой визуализации того, как она работает:
<?php function my_usort($A, $comparator) { // Start .. End Positions $current_pos = 0; $last_pos = count($A)-1; // Outer Loop: each step checks that A[0] up to A[current_pos] is sorted. // When the algorithm finishes we know that A[0] ... A[last_pos] is sorted while($current_pos < $last_pos) { echo "Sorted Subarray from \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n"; echo "\$A looks like this now: " . json_encode($A) . ", comparing [" . $A[$current_pos] . "," . $A[$current_pos +1] . "] (verify step)<br>\n"; // "Verification Step" // At this point A[0] ... A[current_pos] is sorted. // Check A[current_pos] <= A[current_pos +1] if($comparator($A[$current_pos], $A[$current_pos +1]) > 0) { // nope, A[current_pos] > A[current_pos +1] (list_cmp/comparator returns value > 0) // "Insertion Step" start, find the correct position for A[current_pos+1] in the already // sorted list A[0] ... A[current_pos] $insert_point = $current_pos; // Swap the missmatching Neighbor pair echo "swapping: \$A[" . $insert_point . "] and \$A[" . ($insert_point+1) . "]<br>\n"; $tmp = $A[$insert_point +1]; $A[$insert_point +1] = $A[$insert_point]; $A[$insert_point] = $tmp; $sorted_up_to_current_pos = false; // Inner Loop: find correct insertion point while($insert_point > 0 && !$sorted_up_to_current_pos) { echo "\$A looks like this now: " . json_encode($A) . ", comparing [" . $A[$insert_point-1] . "," . $A[$insert_point] . "] (insertion step)<br>\n"; // "Insertion Step", Swap the missmatching Neighbor pairs until A[0] ... A[current_pos] is sorted again if($comparator($A[$insert_point-1], $A[$insert_point]) > 0) { // Swap the missmatching Neighbor pair echo "swapping: \$A[" . ($insert_point-1) . "] and \$A[" . $insert_point . "]<br>\n"; $tmp = $A[$insert_point]; $A[$insert_point] = $A[$insert_point-1]; $A[$insert_point-1] = $tmp; // goto new pair $insert_point = $insert_point -1; } else { // found correct spot, done $sorted_up_to_current_pos = true; } } $A[$insert_point] = $tmp; echo "\$A looks like this now: " . json_encode($A) . ", insertion done<br>\n"; } $current_pos = $current_pos + 1; } echo "Sorted Array \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n"; } function list_cmp($a, $b) { global $order; //echo "\$a=$a, \$b=$b </br>\n"; foreach ($order as $key => $value) { //echo "\$value=$value </br>\n"; if ($a == $value) { echo "\$a=\$value, returing 0. </br>\n"; return 0; } if ($b == $value) { echo "\$b=\$value, returing 1. </br>\n"; return 1; } } } $order[0] = 1; $order[1] = 3; $order[2] = 4; $order[3] = 2; $array[0] = 2; $array[1] = 1; $array[2] = 3; $array[3] = 4; $array[4] = 2; $array[5] = 1; $array[6] = 2; my_usort($array, "list_cmp");
Теперь результат завершен с отсортированным массивом, позиции:
Sorted Subarray from $A is [2] $A looks like this now: [2,1,3,4,2,1,2], comparing [2,1] (verify step) $b=$value, returing 1. swapping: $A[0] and $A[1] $A looks like this now: [1,2,3,4,2,1,2], insertion done Sorted Subarray from $A is [1,2] $A looks like this now: [1,2,3,4,2,1,2], comparing [2,3] (verify step) $b=$value, returing 1. swapping: $A[1] and $A[2] $A looks like this now: [1,3,2,4,2,1,2], comparing [1,3] (insertion step) $a=$value, returing 0. $A looks like this now: [1,3,2,4,2,1,2], insertion done Sorted Subarray from $A is [1,3,2] $A looks like this now: [1,3,2,4,2,1,2], comparing [2,4] (verify step) $b=$value, returing 1. swapping: $A[2] and $A[3] $A looks like this now: [1,3,4,2,2,1,2], comparing [3,4] (insertion step) $a=$value, returing 0. $A looks like this now: [1,3,4,2,2,1,2], insertion done Sorted Subarray from $A is [1,3,4,2] $A looks like this now: [1,3,4,2,2,1,2], comparing [2,2] (verify step) $a=$value, returing 0. Sorted Subarray from $A is [1,3,4,2,2] $A looks like this now: [1,3,4,2,2,1,2], comparing [2,1] (verify step) $b=$value, returing 1. swapping: $A[4] and $A[5] $A looks like this now: [1,3,4,2,1,2,2], comparing [2,1] (insertion step) $b=$value, returing 1. swapping: $A[3] and $A[4] $A looks like this now: [1,3,4,1,2,2,2], comparing [4,1] (insertion step) $b=$value, returing 1. swapping: $A[2] and $A[3] $A looks like this now: [1,3,1,4,2,2,2], comparing [3,1] (insertion step) $b=$value, returing 1. swapping: $A[1] and $A[2] $A looks like this now: [1,1,3,4,2,2,2], comparing [1,1] (insertion step) $a=$value, returing 0. $A looks like this now: [1,1,3,4,2,2,2], insertion done Sorted Subarray from $A is [1,1,3,4,2,2] $A looks like this now: [1,1,3,4,2,2,2], comparing [2,2] (verify step) $a=$value, returing 0. Sorted Array $A is [1,1,3,4,2,2,2]