您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > php

PHP usort 函数底层排序

时间:2020-05-03 10:16:13  来源:  作者:

引出

最近在一个项目中, 需要对一个数组的顺序进行调整, 允许手动将某一个元素提到数组的开头位置. 在这里, 使用了php中的usort函数进行了数组的排序, 代码大致如下:

usort($arr, function ($a, $b){
  // 这里添加了 order 字段, 默认为0, 将order大的提到前边
    return $b['order'] - $a['order'];
});

但是, 今天我大哥突然告诉我, php的usort是不稳定的, 也就是在两个元素相等的情况下, 不能够保证两个元素的位置不变.

在我想到的排序算法中: 选择, 冒泡, 插入, 快排, 希尔, 堆排, 计数, 归并, 其中可以稳定排序的算法有: 冒泡, 插入, 归并. 而这几个算法, 时间复杂度较小的是: 快排, 归并, 堆排. 时间复杂度是O(log n). 如果要选择一款既能够保证稳定性, 时间复杂度又小的算法, 二者取交集也得选择 归并 吧.

但是, 毕竟我不是PHP作者, 咱也不知道人家到底用的是什么, 于是乎, 我决定实验一下, 下面这段代码产生了:

// 生成一个随机数组
$arr = [];
for ($j = 0; $j < 100; $j++){
    $arr[] = [
        'id' => $j,
        'order' => random_int(0, 3),
    ];
}
// 按照order进行排序
usort($arr, function ($a, $b){
    return $b['order'] - $a['order'];
});
// 验证是否稳定
$lastValue = null;
foreach ($arr as $value){
    if(empty($lastValue)){
        $lastValue = $value;
        continue;
    }
    // 若当前元素与上一个元素order相同, 判断
    if($value['order'] == $lastValue['order']){
        // 当前不稳定了, 把数组打印出来
        if($value['id'] < $lastValue['id']){
            echo '不稳定', PHP_EOL;
            exit;
        }
    }
    $lastValue = $value;
}

经过验证, 果然, 我哥诚不欺我. 但是, 我记得我之前也测试过, 数组顺序没有变化啊, 我尝试将数组的长度缩小为4, 突然发现, 是我错了.

分析

既然确定了usort函数是不稳定的排序, 那么他到底是如何进行排序的呢? 我决定尝试着到PHP的源码中挑战一下.

到PHP官方 https://www.php.net/downloads 将源码下载下来. 解压完了也没太看懂目录结构, 既然知道是C语言写的, 尝试文件夹搜索 array.c , 嗯, 搜到了, 将文件打开. 搜索 usort. 嗯, 有的.

PHP usort 函数底层排序

 

再去 php_usort 函数看看:

static void php_usort(INTERNAL_FUNCTION_PARAMETERS, compare_func_t compare_func, zend_bool renumber) /* {{{ */
{
	zval *array;
	zend_array *arr;
	zend_bool retval;
	PHP_ARRAY_CMP_FUNC_VARS;

	PHP_ARRAY_CMP_FUNC_BACKUP();

	// 这个 zend 打头的函数一看就是虚拟机相关的, 不管了
	ZEND_PARSE_PARAMETERS_START(2, 2)
		Z_PARAM_ARRAY_EX2(array, 0, 1, 0)
		Z_PARAM_FUNC(BG(user_compare_fci), BG(user_compare_fci_cache))
	ZEND_PARSE_PARAMETERS_END_EX( PHP_ARRAY_CMP_FUNC_RESTORE(); return );


	arr = Z_ARR_P(array);
	// 一看就是对数组进行判空, 跳过
	if (zend_hash_num_elements(arr) == 0)  {
		PHP_ARRAY_CMP_FUNC_RESTORE();
		RETURN_TRUE;
	}

	/* Copy array, so the in-place modifications will not be visible to the callback function */
	arr = zend_array_dup(arr);

	// 真正进行排序的方法
	retval = zend_hash_sort(arr, compare_func, renumber) != FAILURE;

	// 一些善后操作
	zval_ptr_dtor(array);
	ZVAL_ARR(array, arr);

	PHP_ARRAY_CMP_FUNC_RESTORE();
	RETURN_BOOL(retval);
}

简单看了一下, 找到真正的排序方法zend_hash_sort, OK, 再去这个函数里看看. 那么问题来了, 这个函数在哪呢? 找不到? 暴力破解, 简单写了个Python代码, 将所有文件中带有 zend_hash_sort 的文件都打印出来:

PHP usort 函数底层排序

 

很幸运, 在第一个文件中就找到了.

PHP usort 函数底层排序

 

什么? 是个宏? OK, 正好刚写了程序, 我再重新找一下 zend_hash_sort_ex 函数在哪里.

经过一番苦苦寻找, 终于在 Zend/zend_hash.c 文件下找到了最终的排序算法. 其他的没看懂, 但是, 这里有一句我知道, 是排序的关键:

PHP usort 函数底层排序

 

好吧, 又去调 sort函数, 通过查看, 这个sort函数是本函数的第二个参数, 那在返回去看zend_hash_sort的宏定义, 嗯, 是 zend_sort 函数, 成吧, 再去找这个函数. 发现并不在这两个文件下, 再动用我临时写的Python脚本(这都用三次了, 要不我把他好好封装一下??). 最终在Zend/zend_sort.c 文件中找到. 到此, 原谅我太菜了, 在自己阅读并进行了大量搜索之后, 还是没太看懂排序的流程.

不过, 虽然代码没看懂, 但是, 排序选择的算法我知道了

  1. 若数组长度小于等于16, 使用 插入排序
  2. 若数据长度大于16, 使用 快速排序 (快速排序对元素个数1024前后做了不同的处理, 应该是优化)

总结

再回想一下, 最开始的问题, 当数组长度小于4的时候, 顺序没有改变, 这个因为使用了稳定的插入排序. 当数组长度100的时候, 使用了不稳定的快速排序.

之后使用usort函数, 就把他当做不稳定的就可以了. 这样基本不会有问题的. 但是, 讲话了, 如果我就是需要一个稳定的排序算法怎么办?

来来来, 官方函数推荐给你https://www.php.net/manual/zh/function.uasort.php

If you want to keep the order when two members compare as equal, use this.
<?php

function stable_uasort(&$array, $cmp_function) {
    if(count($array) < 2) {
        return;
    }
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway, TRUE);
    $array2 = array_slice($array, $halfway, NULL, TRUE);

    stable_uasort($array1, $cmp_function);
    stable_uasort($array2, $cmp_function);
    if(call_user_func($cmp_function, end($array1), reset($array2)) < 1) {
        $array = $array1 + $array2;
        return;
    }
    $array = array();
    reset($array1);
    reset($array2);
    while(current($array1) && current($array2)) {
        if(call_user_func($cmp_function, current($array1), current($array2)) < 1) {
            $array[key($array1)] = current($array1);
            next($array1);
        } else {
            $array[key($array2)] = current($array2);
            next($array2);
        }
    }
    while(current($array1)) {
        $array[key($array1)] = current($array1);
        next($array1);
    }
    while(current($array2)) {
        $array[key($array2)] = current($array2);
        next($array2);
    }
    return;
}

简单看了一下, 就是一个标准的归并排序.

这次是我的失误, 当初其实想到了排序的稳定性问题, 然后写了个demo验证了一下(就是长度为4的数组), 然后自认为是稳定的, 其实随便到网上搜一下, 都能搜到的问题的. 引以为鉴.


最后, 当我google找了一下, 发现第一条搜索就告诉了我, PHP的排序对不同长度分别使用了不同的排序算法. 这就尴尬了. 么事, 虽然最后对算法也没完全看懂, 但乐在其中



Tags:PHP usort   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
▌简易百科推荐
序言:前段时间织梦因为版权的问题在网上闹得沸沸扬扬,也提醒了众多开发者选择cms上应该谨慎使用,今天给大家展示一款自己搭建的内容管理系统,不用担心版权的问题,而且非常容易维...【详细内容】
2021-11-30  小程序软件开发    Tags:管理系统   点击:(34)  评论:(0)  加入收藏
准备安装包(PHP: Hypertext Preprocessor)下载安装包以及组件wget https://www.php.net/distributions/php-8.0.0.tar.bz2wget https://github.com/phpredis/phpredis/archive...【详细内容】
2021-11-09  mimic96    Tags:PHP   点击:(40)  评论:(0)  加入收藏
golang context 很好用,就使用php实现了github地址 : https://github.com/qq1060656096/php-go-context context使用闭坑指南1. 将一个Context参数作为第一个参数传递给传入和...【详细内容】
2021-11-05  1060656096    Tags:PHP   点击:(41)  评论:(0)  加入收藏
一段数组为例:$list = array:4 [ 0 => array:7 [ "id" => 56 "mer_id" => 7 "order_id" => "wx163265961408769974" "is_postage" => 0 "store_name" => "奇...【详细内容】
2021-09-29  七七小影视    Tags:PHP   点击:(65)  评论:(0)  加入收藏
利用JS的CryptoJS 3.x和PHP的openssl_encrypt,openssl_decrypt实现AES对称加密解密,由于需要两种语言对同一字符串的操作,而CryptoJS 的默认加密方式为“aes-256-cbc”,PHP端也...【详细内容】
2021-09-16  李老师tome    Tags:对称加密   点击:(79)  评论:(0)  加入收藏
1、checkdate()验证格利高里日期即:日期是否存在。checkdate(month,day,year);month必需。一个从 1 到 12 的数字,规定月。day必需。一个从 1 到 31 的数字,规定日。year必需。...【详细内容】
2021-08-31  七七小影视    Tags:时间函数   点击:(80)  评论:(0)  加入收藏
对于各类开发语言来说,整数都有一个最大的位数,如果超过位数就无法显示或者操作了。其实,这也是一种精度越界之后产生的精度丢失问题。在我们的 PHP 代码中,最大的整数非常大,我...【详细内容】
2021-08-26  硬核项目经理    Tags:PHP   点击:(83)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  硬核项目经理    Tags:线性表   点击:(94)  评论:(0)  加入收藏
一、开启IIS全部功能。二、部署PHP1.官网下载并解压PHP: https://windows.php.net/downloads/releases/2.将php.ini-development文件改为php.ini3.修改php.ini(1)去掉注释,并修...【详细内容】
2021-07-15  炘蓝火诗  今日头条  Tags:PHP环境   点击:(129)  评论:(0)  加入收藏
一、环境说明本文中使用本地VM虚机部署测试。OS:CentOS Linux release 7.8.2003 (Core)虚机配置:2核CPU、4G内存①系统为CentOS 7.8 x64最小化安装,部署前已完成系统初始化、...【详细内容】
2021-06-25  IT运维笔记  今日头条  Tags:PHP8.0.7   点击:(141)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条