Gedanken zur Stabilität der PHP-Sortierung!

稳PHP-Sortierstabilitätsproblem

Bei der Arbeit ist kürzlich ein sehr interessantes Problem aufgetreten. Die Online-Eingabe ist eine Reihe sequentieller verknüpfter Arrays, die nicht lokal reproduziert werden können. Nach der Überprüfung des entsprechenden Codes ist dieser Absatz am interessantesten:

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

Die Funktion besteht darin, das Element gemäß der default-Priorität in den Vordergrund zu bringen. Bestätigen Sie zunächst die Beleuchtung/Unterstützung Die Version stimmt mit der lokalen überein:

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

Am Ende rufe ich immer noch den asort, aber die lokalen und Testergebnisse sind unterschiedlich. Kürzlich habe ich über ein Upgrade auf PHP7 nachgedacht. Schließlich wurde es erfolgreich in der PHP5-Umgebung reproduziert und es wurde festgestellt, dass es sich um eine sort Problem. 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

Die relative Position gleicher Elemente vor und nach der Sortierung ändert sich nicht, was bedeutet, dass dieser Algorithmus stabil ist.

Wenn Sie ein gewisses Verständnis für die schnelle Sortierung haben, wissen Sie, dass die schnelle Sortierung instabil ist, sodass die Ausgabe dieses Codes nicht in der vorherigen Reihenfolge erfolgt, wenn die Prioritäten der Elemente default sind Dasselbe, aber warum behalten die Testergebnisse die ursprüngliche Reihenfolge in der PHP7-Umgebung bei? Liege ich falsch mit dem, was ich vorher verstanden habe, dass alle Standardsortierungen auf der Welt eine schnelle Sortierung sind?🎜🎜Okay, lass es uns schnell machen. Schau es dir an wie der PHP-Quellcode dieses Problem löst. Gehen Sie zum offiziellen PHP-SRC von Github und suchen Sie in diesem Repository direkt nach asort, suchen Sie die C-Datei und finden Sie diese in arr.c:814 definierte Funktion🎜rrreee🎜Sie können sehen, dass das Finale Aufruf ist zend_hash_sort( ), wir suchen weiter: 🎜🎜🎜🎜Ich habe herausgefunden, dass diese Funktion eine verschachtelte Puppe von zend_hash_sort_ex() ist, und habe schließlich zend_hash.c:2497🎜rrreee gefunden 🎜Gut ! In den offiziellen Kommentaren wird erläutert, wie die Stabilität der Sortierung erreicht werden kann. Verwenden Sie vor dem Sortieren dieses Z_EXTRA, um die Zuordnung der ursprünglichen Array-Elemente zu den Indizes beizubehalten. 🎜🎜Aber als ich nach den Übermittlungsinformationen dieses Codes gesucht habe, habe ich ein Problem gefunden: Der RFC im Zusammenhang mit der stabilen Sortierung befindet sich unter https://wiki.php.net/rfc/stable_sorting. Sie können sehen, dass dies im Mai passiert ist Jahr und gezielt php8.0 von. 🎜🎜?? Was ist mit der bisherigen PHP7-Sortierstabilität passiert? 🎜🎜Erstellen Sie sofort ein Beispiel: 🎜rrreee🎜Nach vielen Tests unter PHP7 haben wir festgestellt, dass die Sortierung stabil ist, wenn $count relativ klein ist, $countDie Sortierung jedoch in größeren Fällen wird es wieder instabil. Das heißt, die Online-Sortierung ist instabil und kann nicht lokal reproduziert werden, da die Array-Länge des Anwendungsfalls zu kurz ist. 🎜🎜Angesichts dessen kann ich bestätigen, dass es sich um ein Problem der schnellen Optimierung des Sortierlängenschwellenwerts handelt, und habe schließlich die relevanten Informationen überprüft. sort in PHP7 basiert auf der std::sort-Implementierung von libc++ in LLVM. Wenn die Anzahl der Elemente kleiner oder gleich 16 ist, gibt es eine spezielle Optimierung. Wenn die Anzahl der Elemente größer als 16 ist, wird eine schnelle Sortierung durchgeführt, während PHP5 die schnelle Sortierung direkt verwendet. 🎜rrreee🎜🎜Endlich in einer PHP8-Umgebung ausprobiert, die Sortierung ist absolut stabil🎜🎜

Das obige ist der detaillierte Inhalt vonGedanken zur Stabilität der PHP-Sortierung!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!