PHPソートの安定性についての考察！

PHP ソートの安定性の問題

私は最近、仕事中に非常に興味深い問題に遭遇しました。オンライン入力は、ソートされた連想配列のシーケンスです。一連の後の配列出力です。処理の順序が乱れているため、ローカルで実行すると再現できません。関連するコードを確認した後、最も懸念されるのはこの段落です:

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

は、default の優先順位に従って要素を最前面に移動するために使用されます。 /supportバージョンはローカルのものと一致しています。Arr::sort()ソースコード:

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

を確認してください。最終的には、php の

asort が呼び出され、オンラインが php5 です。最近のアップグレードの考慮により、ローカルとテストの両方が php7 に置き換えられました。最終的には、php5 環境で正常に再現され、sort の問題であることが判明しました。

ソートの前後で等しい要素の相対位置は変化しません。これは、このアルゴリズムが安定していることを意味します。

クイック ソートについてある程度の理解がある場合は、クイック ソートが不安定であることがわかるため、要素

default が同じである場合には、このコードの出力は行われません。前の順序ですが、php7 環境ではテスト結果が元の順序を保持しているのはなぜですか。 世界中のデフォルトの並べ替えはすべてクイック ソートであると理解していたのは間違っていますか?

さて、PHP ソース コードがこの問題をどのように解決するかを簡単に見てみましょう。 github の公式 php-src にアクセスし、このリポジトリで

asort を直接検索し、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 にあります。今年の 5 月に起こりました。そして 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 中国語 Web サイトの他の関連記事を参照してください。