Réflexions sur la stabilité du tri PHP !

稳Problème de stabilité du tri Php

a récemment rencontré un problème très intéressant dans le travail. La saisie en ligne est une série de tableaux associés séquentiels qui ne peuvent pas être reproduits localement. Après avoir vérifié le code concerné, le plus intéressant est ce paragraphe :

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

La fonction est de mettre l'élément au premier plan selon la priorité default. Tout d'abord, confirmez le illuminate/support. < sur la ligne hors ligne. /code>La version est cohérente avec la version locale. Vérifiez le code source de <code>Arr::sort() :

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

Au final, j'appelle toujours le asort. La version en ligne est php5, mais les résultats locaux et ceux des tests sont différents. Récemment, j'ai envisagé de passer à php7. Finalement, elle a été reproduite avec succès dans l'environnement php5 et il a été déterminé qu'il s'agissait d'un <. problème de code>tri. 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

La position relative des éléments égaux avant et après le tri ne change pas, ce qui signifie que cet algorithme est stable.

Si vous avez une certaine compréhension du tri rapide, vous pouvez savoir que le tri rapide est instable, donc la sortie de ce code ne sera pas dans l'ordre précédent lorsque les priorités des éléments default sont la même chose, mais pourquoi les résultats des tests conservent-ils l'ordre d'origine dans l'environnement php7. Est-ce que je me trompe sur ce que j'ai compris auparavant, à savoir que tous les tris par défaut dans le monde sont des tris rapides ?🎜🎜D'accord, faisons-le vite Jetez un oeil comment le code source php résout ce problème. Allez sur le php-src officiel de github et recherchez directement asort dans ce référentiel, trouvez le fichier c et trouvez cette fonction définie dans arr.c:814🎜rrreee🎜Vous pouvez voir que le final l'appel est zend_hash_sort( ), nous continuons à chercher : 🎜🎜🎜🎜J'ai trouvé que cette fonction est une poupée gigogne de zend_hash_sort_ex(), et j'ai finalement trouvé zend_hash.c:2497🎜rrreee 🎜Bien ! , les commentaires officiels expliquent comment obtenir la stabilité du tri. Avant le tri, utilisez ce Z_EXTRA pour conserver le mappage des éléments du tableau d'origine aux indices. 🎜🎜Mais lorsque j'ai recherché les informations de soumission de ce code, j'ai trouvé un problème : la rfc liée au tri stable se trouve sur https://wiki.php.net/rfc/stable_sorting. Vous pouvez voir que cela s'est produit en mai dernier. année et ciblé php8 0 de. 🎜🎜 ?? Alors pourquoi le tri php7 précédent était-il stable ? 🎜🎜Construisez immédiatement un exemple : 🎜rrreee🎜Après de nombreux tests sous php7, nous avons constaté que lorsque $count est relativement petit, le tri est stable, mais $countLe tri dans les cas plus importants, il redevient instable. Autrement dit, le tri en ligne est instable et ne peut pas être reproduit localement car la longueur du tableau du cas d'utilisation est trop courte. 🎜🎜Voyant cela, je peux confirmer qu'il s'agit d'un problème d'optimisation du seuil de longueur de tri rapide, et j'ai finalement vérifié les informations pertinentes. sort dans php7 est basé sur l'implémentation std::sort de libc++ dans LLVM. Il y a une optimisation particulière lorsque le nombre d'éléments est inférieur ou égal à 16. Si le nombre d'éléments est supérieur à 16, un tri rapide sera effectué, tandis que php5 utilisera directement le tri rapide. 🎜rrreee🎜🎜Enfin essayé dans l'environnement php8, le tri est absolument stable🎜🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!