对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_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()
,我们继续搜索:
发现这个函数是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
保留了原数组元素到下标的映射。
但当我搜索这块代码提交信息时发现了一个问题:稳定排序相关的 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
是基于LLVM
中libc++
的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排序稳定性问题的深思!的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

如果您是一位经验丰富的 PHP 开发人员,您可能会感觉您已经在那里并且已经完成了。您已经开发了大量的应用程序,调试了数百万行代码,并调整了一堆脚本来实现操作

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

JWT是一种基于JSON的开放标准,用于在各方之间安全地传输信息,主要用于身份验证和信息交换。1.JWT由Header、Payload和Signature三部分组成。2.JWT的工作原理包括生成JWT、验证JWT和解析Payload三个步骤。3.在PHP中使用JWT进行身份验证时,可以生成和验证JWT,并在高级用法中包含用户角色和权限信息。4.常见错误包括签名验证失败、令牌过期和Payload过大,调试技巧包括使用调试工具和日志记录。5.性能优化和最佳实践包括使用合适的签名算法、合理设置有效期、

字符串是由字符组成的序列,包括字母、数字和符号。本教程将学习如何使用不同的方法在PHP中计算给定字符串中元音的数量。英语中的元音是a、e、i、o、u,它们可以是大写或小写。 什么是元音? 元音是代表特定语音的字母字符。英语中共有五个元音,包括大写和小写: a, e, i, o, u 示例 1 输入:字符串 = "Tutorialspoint" 输出:6 解释 字符串 "Tutorialspoint" 中的元音是 u、o、i、a、o、i。总共有 6 个元

本教程演示了如何使用PHP有效地处理XML文档。 XML(可扩展的标记语言)是一种用于人类可读性和机器解析的多功能文本标记语言。它通常用于数据存储

静态绑定(static::)在PHP中实现晚期静态绑定(LSB),允许在静态上下文中引用调用类而非定义类。1)解析过程在运行时进行,2)在继承关系中向上查找调用类,3)可能带来性能开销。

PHP的魔法方法有哪些?PHP的魔法方法包括:1.\_\_construct,用于初始化对象;2.\_\_destruct,用于清理资源;3.\_\_call,处理不存在的方法调用;4.\_\_get,实现动态属性访问;5.\_\_set,实现动态属性设置。这些方法在特定情况下自动调用,提升代码的灵活性和效率。
