对PHP排序稳定性问题的深思！
发布时间：2022-08-11 11:24:01 所属栏目：教程 来源：互联网
导读：PHP排序稳定性问题 最近在工作中碰到一个挺有意思的问题，线上输入是一串排好序的关联数组，经过一系列处理后输出的数组却是乱序，且本地运行无法复现。查看相关代码后，最让人在意的是这一段: $categories = Arr::sort($categories, function ($node) { ret
|
PHP排序稳定性问题 最近在工作中碰到一个挺有意思的问题，线上输入是一串排好序的关联数组，经过一系列处理后输出的数组却是乱序，且本地运行无法复现。查看相关代码后，最让人在意的是这一段: $categories = Arr::sort($categories, function ($node) { return $node['default']; }, true); 作用是按default优先级将元素提到前面，首先确认了下线上的illuminate/support版本和本地一致，查看Arr::sort()源码: ... $descending ? arsort($results, $options) : asort($results, $options); 最终还是调用 php 的asort，线上是 php5 而本地和测试因为最近考虑升级都换成了 php7，最后在 php5 环境下成功复现，确定出是sort问题。 在排序前后相等的元素相对位置不变即说这个算法是稳定的。 对快速排序有一定了解的话可以知道，快速排序是不稳定的所以这段代码在元素default优先级都相同的情况下输出将不会是之前的顺序，但在 php7 环境下测试结果为什么会保留原来的顺序呢。难道关于我之前理解的天底下所有默认排序都是快速排序这一点是错的吗? 好吧，让我们来快速看看 php 源码是如何解决这个问题的。到 github 官方的 php-src 直接搜索asort in this repository，找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()，我们继续搜索: 57c0d1777ab497e3e29e95dc6c1a55e.png 发现这个函数是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保留了原数组元素到下标的映射。 （编辑：无锡站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |