對PHP排序穩定性問題的深思！

PHP排序穩定問題             

最近在工作中碰到一個挺有意思的問題，線上輸入是一串排好序的關聯數組，經過一階系列處理後輸出的陣列卻是亂序，且本機運作無法重現。查看相關程式碼後，最讓人在意的是這段:

$categories = Arr::sort($categories, function ($node) {
    return $node['default'];
}, true);

作用是按default優先權將元素提到前面，先確認了下線上的illuminate /support版本和本地一致，查看Arr::sort()原始碼:

...
$descending ? arsort($results, $options)
            : asort($results, $options);

最終還是呼叫php 的asort，線上是php5 而本地和測試因為最近考慮升級都換成了php7，最後在php5 環境下成功復現，確定出是sort問題。

在排序前後相等的元素相對位置不變即說這個演算法是穩定的。

對快速排序有一定了解的話可以知道，快速排序是不穩定的所以這段程式碼在元素default優先順序都相同的情況下輸出將不會是之前的順序，但在php7 環境下測試結果為什麼要保留原來的順序。 難道關於我之前理解的天底下所有預設排序都是快速排序這一點是錯的嗎?

好吧，讓我們來快速看看php 原始碼是如何解決這個問題的。到github 官方的php-src 直接搜尋asort in this repository，找c文件，找到這個函數定義在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();

	// 设置比较函数
	cmp = php_get_data_compare_func(sort_type, 0);

	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);

	RETURN_TRUE;
}

可以看到最終呼叫的是zend_hash_sort()，我們繼續搜尋:

發現這個函數是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指数组元素被unset掉产生的洞
	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)));
	...

好耶！ ，官方註解裡就有說明是怎麼實現排序的穩定性，在排序之前用這個Z_EXTRA保留了原始數組元素到下標的映射。

但當我搜尋這塊程式碼提交資訊時發現了一個問題：穩定排序相關的rfc 在https://wiki.php.net/rfc/stable_sorting，可以看到是發生在今年五月且針對php8.0 的。

?? 那之前的 php7 排序穩定是怎麼回事。

馬上建構一個例子：

$count = 10;
$cc = [];
for ($i=0; $i<$count; $i++) {
    $cc[] = [
        &#39;id&#39; => $i,
        &#39;default&#39; => rand(0, 10),
    ];
}
$cc = Arr::sort($cc, function ($i) {
   return $i[&#39;default&#39;];
});
dd($cc);

經過多次在php7 下的測試發現：當$count比較小的時候，排序才是穩定的，但$count較大情況下的排序又變成不穩定。也就是線上排序不穩定而本地無法復現其實是用例的陣列長度太短所致。

看到這裡可以確定是快速排序長度閾值最佳化的問題，最後查了下相關資料。 php7 中的sort是基於LLVM中libc 的std::sort實作。當元素數量小於等於16時候有特殊最佳化，大於16才走快速排序，而 php5 是直接就走快速排序的。

<?php

$count = 100;
$cc = [];
for ($i=0; $i<$count; $i++) {
    $cc[] = [
        &#39;id&#39; => $i,
        &#39;default&#39; => rand(0, 10),
    ];
}
usort($cc, function($a, $b){
    if ($a[&#39;default&#39;] == $b[&#39;default&#39;]) return 0;
    return ($a[&#39;default&#39;] < $b[&#39;default&#39;]) ? 1 : -1;
});
print_r($cc);

最後在 php8 環境下試了試，排序絕對穩定

#

以上是對PHP排序穩定性問題的深思！的詳細內容。更多資訊請關注PHP中文網其他相關文章！