Fikiran tentang kestabilan pengisihan PHP!

Masalah kestabilan pengisihan PHP  

Baru-baru ini saya menghadapi masalah yang menarik di tempat kerja Input dalam talian ialah urutan tatasusunan bersekutu yang diisih selepas pemprosesan siri tidak teratur, dan tidak boleh diterbitkan semula apabila dijalankan secara tempatan. Selepas menyemak kod yang berkaitan, bahagian yang paling membimbangkan ialah perenggan ini:

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

digunakan untuk membawa elemen ke hadapan mengikut keutamaan default Mula-mula, sahkan versi illuminate/support luar talian dan setempat versi Konsisten, semak Arr::sort() kod sumber:

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

Pada akhirnya, ia adalah asort yang dipanggil PHP Versi dalam talian ialah PHP5. Walau bagaimanapun, hasil tempatan dan ujian telah digantikan dengan PHP7 disebabkan pertimbangan naik taraf baru-baru ini, akhirnya, ia berjaya dalam persekitaran PHP5 dan ia telah ditentukan untuk menjadi masalah sort.

Kedudukan relatif elemen yang sama sebelum dan selepas pengisihan tidak berubah, yang bermaksud bahawa algoritma ini adalah stabil.

Jika anda mempunyai pemahaman tertentu tentang isihan pantas, anda boleh tahu bahawa isihan pantas adalah tidak stabil, jadi output kod ini tidak akan berada dalam susunan sebelumnya apabila keutamaan elemen default adalah sama. Tetapi mengapa keputusan ujian mengekalkan susunan asal dalam persekitaran php7. Adakah saya salah tentang apa yang saya faham sebelum ini bahawa semua pengisihan lalai di dunia adalah pengisihan pantas?

Baiklah, mari kita lihat dengan pantas cara kod sumber php menyelesaikan masalah ini. Pergi ke php-src rasmi github dan cari terus asort dalam repositori ini, cari fail c dan cari fungsi ini ditakrifkan dalam 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;
}

Anda boleh melihatnya panggilan terakhir ialah zend_hash_sort() Kami terus mencari:

dan mendapati bahawa fungsi ini ialah anak patung bersarang zend_hash_sort_ex(), dan akhirnya menemui 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)));
	...

Baik! , ulasan rasmi menerangkan cara mencapai kestabilan pengisihan Sebelum mengisih, gunakan Z_EXTRA ini untuk mengekalkan pemetaan elemen tatasusunan asal kepada subskrip.

Tetapi apabila saya mencari maklumat penyerahan kod ini, saya mendapati masalah: rfc yang berkaitan dengan pengisihan stabil adalah di https://wiki.php.net/rfc/stable_sorting Anda boleh melihatnya berlaku pada bulan Mei tahun ini dan untuk php8.0.

?? Apakah yang berlaku kepada kestabilan pengisihan php7 sebelumnya?

Segera bina contoh:

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

Selepas banyak ujian di bawah php7, didapati bahawa apabila $count agak kecil, pengisihan adalah stabil, tetapi $count lebih besar. pengisihan dalam kes besar menjadi tidak stabil semula. Maksudnya, pengisihan dalam talian tidak stabil dan tidak boleh diterbitkan semula secara tempatan kerana panjang tatasusunan kes penggunaan terlalu pendek.

Melihat perkara ini, saya boleh mengesahkan bahawa ini adalah masalah pengoptimuman ambang panjang isihan pantas, dan akhirnya menyemak maklumat yang berkaitan. sort dalam php7 adalah berdasarkan LLVM pelaksanaan libc dalam std::sort. Terdapat pengoptimuman khas apabila bilangan elemen kurang daripada atau sama dengan 16. Jika bilangan elemen lebih daripada 16, pengisihan pantas akan dilakukan Walau bagaimanapun, php5 akan menggunakan pengisihan pantas secara langsung.

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

Akhirnya saya mencubanya dalam persekitaran php8, pengisihan benar-benar stabil

Atas ialah kandungan terperinci Fikiran tentang kestabilan pengisihan PHP!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!