文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

PHP排序稳定性实例分析

2023-06-29 02:12

关注

今天小编给大家分享一下PHP排序稳定性实例分析的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

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_OPTIONALZ_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(),我们继续搜索:

PHP排序稳定性实例分析

发现这个函数是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)) {return;}// 这里的hole指数组元素被unset掉产生的洞if (HT_IS_WITHOUT_HOLES(ht)) {for (i = 0; i < ht->nNumUsed; i++) {Z_EXTRA(ht->arData[i].val) = i;}} else {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保留了原数组元素到下标的映射。

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

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

马上构造个例子:

$count = 10;$cc = [];for ($i=0; $i<$count; $i++) {    $cc[] = [        'id' => $i,        'default' => rand(0, 10),    ];}$cc = Arr::sort($cc, function ($i) {   return $i['default'];});dd($cc);

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

看到这里可以确定是快速排序长度阈值优化的问题,最后查了下相关资料。php7 中的sort是基于LLVMlibc++std::sort实现。当元素数量小于等于16时候有特殊优化,大于16才走快速排序,而 php5 是直接就走快速排序的。

<?php$count = 100;$cc = [];for ($i=0; $i<$count; $i++) {    $cc[] = [        'id' => $i,        'default' => rand(0, 10),    ];}usort($cc, function($a, $b){    if ($a['default'] == $b['default']) return 0;    return ($a['default'] < $b['default']) ? 1 : -1;});print_r($cc);

最后在 php8 环境下试了试,排序绝对稳定

以上就是“PHP排序稳定性实例分析”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯