PHP 정렬의 안정성에 대한 생각입니다!

稳PHP 정렬 안정성 문제

최근 작업에서 매우 흥미로운 문제가 발생했습니다. 온라인 입력은 일련의 순차적 연관 배열을 로컬에서 재현할 수 없습니다. 관련 코드를 확인한 후 가장 우려되는 부분은 다음 단락입니다.

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

default 우선 순위에 따라 요소를 앞으로 가져오는 기능입니다. 먼저 illuminate/support를 확인하세요. 버전이 로컬 버전과 일치합니다. <code>Arr::sort()의 소스 코드를 확인하세요.

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

결국에는 여전히 php의 asort. 온라인 버전은 php5인데 로컬과 테스트 결과가 다릅니다. 최근 php7로 업그레이드를 고려 중이었는데 php5 환경에서 성공적으로 재현한 것으로 확인되었습니다. 코드>정렬 문제. default优先级将元素提到前面，首先确认了下线上的illuminate/support版本和本地一致，查看Arr::sort()源码:

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;
}

最终还是调用 php 的asort，线上是 php5 而本地和测试因为最近考虑升级都换成了 php7，最后在 php5 环境下成功复现，确定出是sort问题。

在排序前后相等的元素相对位置不变即说这个算法是稳定的。

对快速排序有一定了解的话可以知道，快速排序是不稳定的所以这段代码在元素default优先级都相同的情况下输出将不会是之前的顺序，但在 php7 环境下测试结果为什么会保留原来的顺序呢。难道关于我之前理解的天底下所有默认排序都是快速排序这一点是错的吗?

好吧，让我们来快速看看 php 源码是如何解决这个问题的。到 github 官方的 php-src 直接搜索asort in this repository，找c文件，找到这个函数定义在 arr.c:814

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)));
	...

可以看到最终调用的是zend_hash_sort()，我们继续搜索:

发现这个函数是zend_hash_sort_ex()的套娃，最后找到zend_hash.c:2497

$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);

好耶！，官方注释里就有说明是怎么实现排序的稳定性，在排序之前用这个Z_EXTRA保留了原数组元素到下标的映射。

但当我搜索这块代码提交信息时发现了一个问题：稳定排序相关的 rfc 在https://wiki.php.net/rfc/stable_sorting，可以看到是发生在今年五月份且针对 php8.0 的。

?? 那之前的 php7 排序稳定是怎么回事。

马上构造个例子：

<?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);

经过多次在 php7 下的测试发现：当$count比较小的时候，排序才是稳定的，但$count较大情况下的排序又变成不稳定。也就是线上排序不稳定而本地无法复现其实是用例的数组长度太短所致。

看到这里可以确定是快速排序长度阈值优化的问题，最后查了下相关资料。php7 中的sort是基于LLVM中libc++的std::sort

정렬 전후의 동일한 요소의 상대적 위치는 변경되지 않습니다. 이는 이 알고리즘이 안정적이라는 것을 의미합니다.

퀵 정렬에 대해 어느 정도 이해했다면 퀵 정렬이 불안정하다는 것을 알 수 있습니다. 따라서 default 요소의 우선 순위가 다음과 같을 때 이 코드의 출력은 이전 순서가 되지 않습니다. 동일하지만 왜 php7 환경에서는 테스트 결과가 원래 순서를 유지합니까? 세상의 모든 기본 정렬은 퀵 정렬이라는 것을 이전에 제가 이해한 것이 잘못된 것인가요?🎜🎜자, 빨리 해보자 한번 살펴보세요 PHP 소스 코드가 이 문제를 어떻게 해결하는지 살펴보세요. github의 공식 php-src에 가서 이 저장소에서 asort를 직접 검색하고, c 파일을 찾아 arr.c:814🎜rrreee🎜에 정의된 이 함수를 찾으면 최종 결과가 나오는 것을 볼 수 있습니다. 호출은 zend_hash_sort( )입니다. 계속해서 검색합니다: 🎜🎜🎜🎜이 함수가 zend_hash_sort_ex()의 중첩 인형인 것을 발견했고, 마침내 zend_hash.c:2497🎜rrreee를 발견했습니다. 🎜좋아요 ! , 공식 의견에서는 정렬의 안정성을 달성하는 방법을 설명합니다. 정렬하기 전에 이 Z_EXTRA를 사용하여 원래 배열 요소를 아래 첨자에 대한 매핑을 유지합니다. 🎜🎜그런데 이 코드의 제출 정보를 검색해 보니 문제가 발견되었습니다. stable sorting과 관련된 rfc는 https://wiki.php.net/rfc/stable_sorting에 있는데 올해 5월에 발생한 일이라고 볼 수 있습니다. 연도 및 대상 php8 0. 🎜🎜?? 그럼 이전 php7 정렬은 왜 안정적이었나요? 🎜🎜즉시 예제 구성: 🎜rrreee🎜php7에서 여러 테스트를 거친 후 $count가 상대적으로 작을 때 정렬이 안정적이지만 $count정렬이 더 큰 경우에는 다시 불안정해집니다. 즉, 온라인 정렬은 불안정하고 사용 사례의 배열 길이가 너무 짧기 때문에 로컬에서 재현할 수 없습니다. 🎜🎜이를 보면 퀵 정렬 길이 임계값 최적화의 문제임을 확인할 수 있었고, 최종적으로 관련 정보를 확인했습니다. php7의 sort는 LLVM의 libc++의 std::sort 구현을 기반으로 합니다. 요소 수가 16개보다 작거나 같을 때 특별한 최적화가 있습니다. 요소 수가 16보다 크면 빠른 정렬이 수행됩니다. 그러나 php5에서는 빠른 정렬을 직접 사용합니다. 🎜rrreee🎜🎜드디어 php8 환경에서 해봤는데 정렬이 완전 안정적이네요🎜🎜

위 내용은 PHP 정렬의 안정성에 대한 생각입니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!