建站
咨詢
售后
建站咨詢
新聞中心
php排序穩(wěn)定性問題
創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),順慶企業(yè)網(wǎng)站建設(shè),順慶品牌網(wǎng)站建設(shè),網(wǎng)站定制,順慶網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,順慶網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
最近在工作中碰到一個挺有意思的問題，線上輸入是一串排好序的關(guān)聯(lián)數(shù)組，經(jīng)過一系列處理后輸出的數(shù)組卻是亂序，且本地運(yùn)行無法復(fù)現(xiàn)。查看相關(guān)代碼后，最讓人在意的是這一段:
$categories = Arr::sort($categories, function ($node) {
return $node['default'];
}, true);
作用是按default優(yōu)先級將元素提到前面，首先確認(rèn)了下線上的illuminate/support版本和本地一致，查看Arr::sort()源碼:
...
$descending ? arsort($results, $options)
: asort($results, $options);
最終還是調(diào)用 php 的asort，線上是 php5 而本地和測試因為最近考慮升級都換成了 php7，最后在 php5 環(huán)境下成功復(fù)現(xiàn)，確定出是sort問題。
對快速排序有一定了解的話可以知道，快速排序是不穩(wěn)定的所以這段代碼在元素default優(yōu)先級都相同的情況下輸出將不會是之前的順序，但在 php7 環(huán)境下測試結(jié)果為什么會保留原來的順序呢。難道關(guān)于我之前理解的天底下所有默認(rèn)排序都是快速排序這一點(diǎn)是錯的嗎?
好吧，讓我們來快速看看 php 源碼是如何解決這個問題的。到 github 官方的 php-src 直接搜索asort in this repository，找c文件，找到這個函數(shù)定義在 arr.c:814
PHP_FUNCTION(asort)
{
zval *array;
zend_long sort_type = PHP_SORT_REGULAR;
bucket_compare_func_t cmp;
ZEND_PARSE_PARAMETERS_START(1, 2)
Z_PARAM_ARRAY_EX(array, 0, 1)
Z_PARAM_OPTIONAL
Z_PARAM_LONG(sort_type)
ZEND_PARSE_PARAMETERS_END();
// 設(shè)置比較函數(shù)
cmp = php_get_data_compare_func(sort_type, 0);
zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
RETURN_TRUE;
}
可以看到最終調(diào)用的是zend_hash_sort()，我們繼續(xù)搜索:
發(fā)現(xiàn)這個函數(shù)是zend_hash_sort_ex()的套娃，最后找到zend_hash.c:2497
ZEND_API void ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, zend_bool renumber)
{
Bucket *p;
uint32_t i, j;
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) {
/* Doesn't require sorting */
return;
}
// 這里的hole指數(shù)組元素被unset掉產(chǎn)生的洞
if (HT_IS_WITHOUT_HOLES(ht)) {
/* Store original order of elements in extra space to allow stable sorting. */
for (i = 0; i < ht->nNumUsed; i++) {
Z_EXTRA(ht->arData[i].val) = i;
}
} else {
/* Remove holes and store original order. */
for (j = 0, i = 0; j < ht->nNumUsed; j++) {
p = ht->arData + j;
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue;
if (i != j) {
ht->arData[i] = *p;
}
Z_EXTRA(ht->arData[i].val) = i;
i++;
}
ht->nNumUsed = i;
}
sort((void *)ht->arData, ht->nNumUsed, sizeof(Bucket), (compare_func_t) compar,
(swap_func_t)(renumber? zend_hash_bucket_renum_swap :
((HT_FLAGS(ht) & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));
...
好耶！，官方注釋里就有說明是怎么實(shí)現(xiàn)排序的穩(wěn)定性，在排序之前用這個Z_EXTRA保留了原數(shù)組元素到下標(biāo)的映射。
但當(dāng)我搜索這塊代碼提交信息時發(fā)現(xiàn)了一個問題：穩(wěn)定排序相關(guān)的 rfc 在https://wiki.php.net/rfc/stable_sorting，可以看到是發(fā)生在今年五月份且針對 php8.0 的。
?? 那之前的 php7 排序穩(wěn)定是怎么回事。
馬上構(gòu)造個例子：
$count = 10;
$cc = [];
for ($i=0; $i<$count; $i++) {
$cc[] = [
'id' => $i,
'default' => rand(0, 10),
];
}
$cc = Arr::sort($cc, function ($i) {
return $i['default'];
});
dd($cc);
經(jīng)過多次在 php7 下的測試發(fā)現(xiàn)：當(dāng)$count比較小的時候，排序才是穩(wěn)定的，但$count較大情況下的排序又變成不穩(wěn)定。也就是線上排序不穩(wěn)定而本地?zé)o法復(fù)現(xiàn)其實(shí)是用例的數(shù)組長度太短所致。
看到這里可以確定是快速排序長度閾值優(yōu)化的問題，最后查了下相關(guān)資料。php7 中的sort是基于LLVM中libc++的std::sort實(shí)現(xiàn)。當(dāng)元素數(shù)量小于等于16時候有特殊優(yōu)化，大于16才走快速排序，而 php5 是直接就走快速排序的。
$i,
'default' => rand(0, 10),
];
}
usort($cc, function($a, $b){
if ($a['default'] == $b['default']) return 0;
return ($a['default'] < $b['default']) ? 1 : -1;
});
print_r($cc); 新聞標(biāo)題：對PHP排序穩(wěn)定性問題的深思！
URL標(biāo)題：http://www.5511xx.com/article/coepiss.html
