首页 后端开发 php教程 对PHP排序稳定性问题的深思!

对PHP排序稳定性问题的深思!

Feb 06, 2022 am 05:00 AM
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(),我们继续搜索:

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保留了原数组元素到下标的映射。

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

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

马上构造个例子:

$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);
登录后复制

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

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

<?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);
登录后复制

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

以上是对PHP排序稳定性问题的深思!的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

CakePHP 项目配置 CakePHP 项目配置 Sep 10, 2024 pm 05:25 PM

在本章中,我们将了解CakePHP中的环境变量、常规配置、数据库配置和电子邮件配置。

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

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

CakePHP 日期和时间 CakePHP 日期和时间 Sep 10, 2024 pm 05:27 PM

为了在 cakephp4 中处理日期和时间,我们将使用可用的 FrozenTime 类。

CakePHP 文件上传 CakePHP 文件上传 Sep 10, 2024 pm 05:27 PM

为了进行文件上传,我们将使用表单助手。这是文件上传的示例。

CakePHP 路由 CakePHP 路由 Sep 10, 2024 pm 05:25 PM

在本章中,我们将学习以下与路由相关的主题?

讨论 CakePHP 讨论 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的开源框架。它的目的是使应用程序的开发、部署和维护变得更加容易。 CakePHP 基于类似 MVC 的架构,功能强大且易于掌握。模型、视图和控制器 gu

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

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

CakePHP 创建验证器 CakePHP 创建验证器 Sep 10, 2024 pm 05:26 PM

可以通过在控制器中添加以下两行来创建验证器。

See all articles