您的位置 首页 php

PHP usort 函数底层排序

引出

最近在一个项目中, 需要对一个数组的顺序进行调整, 允许手动将某一个元素提到数组的开头位置. 在这里, 使用了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官方 将源码下载下来. 解压完了也没太看懂目录结构, 既然知道是c语言写的, 尝试文件夹搜索 array.c , 嗯, 搜到了, 将文件打开. 搜索 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 的文件都打印出来:

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

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

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

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

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

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

总结

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

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

来来来, 官方函数推荐给你

 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的排序对不同长度分别使用了不同的排序算法. 这就尴尬了. 么事, 虽然最后对算法也没完全看懂, 但乐在其中

文章来源:智云一二三科技

文章标题:PHP usort 函数底层排序

文章地址:https://www.zhihuclub.com/150087.shtml

关于作者: 智云科技

热门文章

网站地图