引出
最近在一個項目中, 需要對一個數組的順序進行調整, 允許手動將某一個元素提到數組的開頭位置. 在這里, 使用了php中的usort函數進行了數組的排序, 代碼大致如下:
usort($arr, function ($a, $b){
// 這里添加了 order 字段, 默認為0, 將order大的提到前邊
return $b['order'] - $a['order'];
});
但是, 今天我大哥突然告訴我, php的usort是不穩定的, 也就是在兩個元素相等的情況下, 不能夠保證兩個元素的位置不變.
在我想到的排序算法中: 選擇, 冒泡, 插入, 快排, 希爾, 堆排, 計數, 歸并, 其中可以穩定排序的算法有: 冒泡, 插入, 歸并. 而這幾個算法, 時間復雜度較小的是: 快排, 歸并, 堆排. 時間復雜度是O(log n). 如果要選擇一款既能夠保證穩定性, 時間復雜度又小的算法, 二者取交集也得選擇 歸并 吧.
但是, 畢竟我不是PHP作者, 咱也不知道人家到底用的是什么, 于是乎, 我決定實驗一下, 下面這段代碼產生了:
// 生成一個隨機數組
$arr = [];
for ($j = 0; $j < 100; $j++){
$arr[] = [
'id' => $j,
'order' => random_int(0, 3),
];
}
// 按照order進行排序
usort($arr, function ($a, $b){
return $b['order'] - $a['order'];
});
// 驗證是否穩定
$lastValue = null;
foreach ($arr as $value){
if(empty($lastValue)){
$lastValue = $value;
continue;
}
// 若當前元素與上一個元素order相同, 判斷
if($value['order'] == $lastValue['order']){
// 當前不穩定了, 把數組打印出來
if($value['id'] < $lastValue['id']){
echo '不穩定', PHP_EOL;
exit;
}
}
$lastValue = $value;
}
經過驗證, 果然, 我哥誠不欺我. 但是, 我記得我之前也測試過, 數組順序沒有變化啊, 我嘗試將數組的長度縮小為4, 突然發現, 是我錯了.
分析
既然確定了usort函數是不穩定的排序, 那么他到底是如何進行排序的呢? 我決定嘗試著到PHP的源碼中挑戰一下.
到PHP官方 https://www.php.net/downloads 將源碼下載下來. 解壓完了也沒太看懂目錄結構, 既然知道是C語言寫的, 嘗試文件夾搜索 array.c , 嗯, 搜到了, 將文件打開. 搜索 usort. 嗯, 有的.
再去 php_usort 函數看看:
static void php_usort(INTERNAL_FUNCTION_PARAMETERS, compare_func_t compare_func, zend_bool renumber) /* {{{ */
{
zval *array;
zend_array *arr;
zend_bool retval;
PHP_ARRAY_CMP_FUNC_VARS;
PHP_ARRAY_CMP_FUNC_BACKUP();
// 這個 zend 打頭的函數一看就是虛擬機相關的, 不管了
ZEND_PARSE_PARAMETERS_START(2, 2)
Z_PARAM_ARRAY_EX2(array, 0, 1, 0)
Z_PARAM_FUNC(BG(user_compare_fci), BG(user_compare_fci_cache))
ZEND_PARSE_PARAMETERS_END_EX( PHP_ARRAY_CMP_FUNC_RESTORE(); return );
arr = Z_ARR_P(array);
// 一看就是對數組進行判空, 跳過
if (zend_hash_num_elements(arr) == 0) {
PHP_ARRAY_CMP_FUNC_RESTORE();
RETURN_TRUE;
}
/* Copy array, so the in-place modifications will not be visible to the callback function */
arr = zend_array_dup(arr);
// 真正進行排序的方法
retval = zend_hash_sort(arr, compare_func, renumber) != FAILURE;
// 一些善后操作
zval_ptr_dtor(array);
ZVAL_ARR(array, arr);
PHP_ARRAY_CMP_FUNC_RESTORE();
RETURN_BOOL(retval);
}
簡單看了一下, 找到真正的排序方法zend_hash_sort, OK, 再去這個函數里看看. 那么問題來了, 這個函數在哪呢? 找不到? 暴力破解, 簡單寫了個Python代碼, 將所有文件中帶有 zend_hash_sort 的文件都打印出來:
很幸運, 在第一個文件中就找到了.
什么? 是個宏? OK, 正好剛寫了程序, 我再重新找一下 zend_hash_sort_ex 函數在哪里.
經過一番苦苦尋找, 終于在 Zend/zend_hash.c 文件下找到了最終的排序算法. 其他的沒看懂, 但是, 這里有一句我知道, 是排序的關鍵:
好吧, 又去調 sort函數, 通過查看, 這個sort函數是本函數的第二個參數, 那在返回去看zend_hash_sort的宏定義, 嗯, 是 zend_sort 函數, 成吧, 再去找這個函數. 發現并不在這兩個文件下, 再動用我臨時寫的Python腳本(這都用三次了, 要不我把他好好封裝一下??). 最終在Zend/zend_sort.c 文件中找到. 到此, 原諒我太菜了, 在自己閱讀并進行了大量搜索之后, 還是沒太看懂排序的流程.
不過, 雖然代碼沒看懂, 但是, 排序選擇的算法我知道了
- 若數組長度小于等于16, 使用 插入排序
- 若數據長度大于16, 使用 快速排序 (快速排序對元素個數1024前后做了不同的處理, 應該是優化)
總結
再回想一下, 最開始的問題, 當數組長度小于4的時候, 順序沒有改變, 這個因為使用了穩定的插入排序. 當數組長度100的時候, 使用了不穩定的快速排序.
之后使用usort函數, 就把他當做不穩定的就可以了. 這樣基本不會有問題的. 但是, 講話了, 如果我就是需要一個穩定的排序算法怎么辦?
來來來, 官方函數推薦給你https://www.php.net/manual/zh/function.uasort.php
If you want to keep the order when two members compare as equal, use this.
<?php
function stable_uasort(&$array, $cmp_function) {
if(count($array) < 2) {
return;
}
$halfway = count($array) / 2;
$array1 = array_slice($array, 0, $halfway, TRUE);
$array2 = array_slice($array, $halfway, NULL, TRUE);
stable_uasort($array1, $cmp_function);
stable_uasort($array2, $cmp_function);
if(call_user_func($cmp_function, end($array1), reset($array2)) < 1) {
$array = $array1 + $array2;
return;
}
$array = array();
reset($array1);
reset($array2);
while(current($array1) && current($array2)) {
if(call_user_func($cmp_function, current($array1), current($array2)) < 1) {
$array[key($array1)] = current($array1);
next($array1);
} else {
$array[key($array2)] = current($array2);
next($array2);
}
}
while(current($array1)) {
$array[key($array1)] = current($array1);
next($array1);
}
while(current($array2)) {
$array[key($array2)] = current($array2);
next($array2);
}
return;
}
簡單看了一下, 就是一個標準的歸并排序.
這次是我的失誤, 當初其實想到了排序的穩定性問題, 然后寫了個demo驗證了一下(就是長度為4的數組), 然后自認為是穩定的, 其實隨便到網上搜一下, 都能搜到的問題的. 引以為鑒.
最后, 當我google找了一下, 發現第一條搜索就告訴了我, PHP的排序對不同長度分別使用了不同的排序算法. 這就尷尬了. 么事, 雖然最后對算法也沒完全看懂, 但樂在其中
