PHP数组取交集的方法对比及性能测试

PHP 作为世界上最好的语言,怎么可能有不完美的地方呢?最近因为业务上的一个需求,遇到了一个求几个大数组交集的场景。在实现的过程中,毫不意外地遭遇了性能问题。这里记录一下关于 PHP 取数组交集的性能优化思考。

不想看过程的可以直接跳到文末看结论。

场景描述

  1. 接口输出一个简单的 list 接口,大概 100+ 行数据,每行数据有 4 个字段都需要进行交集操作。即该接口总共需要进行 400-500 次交集操作。
  2. 进行交集操作的成员数组数据量大概在 2w 左右,全部为数值(类型不敏感,可根据需要转换为 string / int 类型)
  3. 可以使用 redis 作为缓存。

伪代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
<?php
Class List {
    public function list()
    {
        $arr1 = [1,2,3...]; // count($arr1) = 20000
        $arr2 = [3,4,5...]; // count($arr2) = 20000
        foreach ($list as $value) {
            $list['key1'] = intersect($arr1, arr2);
            $list['key2'] = intersect($arr1, arr2);
            $list['key3'] = intersect($arr1, arr2);
            $list['key4'] = intersect($arr1, arr2);
        }
        
        return $list;
    }
}

实现路径

PHP 原生方法

众所周知 PHP 自带了一大堆数组的助手方法可以直接调用,实在是太方便不过了,直接一把梭搞定:

1
array_intersect($arr1, $arr2);

如果这个方法这么好用,我当然也就不用大费周章写这篇文章了。实现归实现,在满足场景需求的情况下,整个接口的响应速度来到了惊人的 30+s。可以说是非常棒了,可以直接气死产品和甲方。

Redis 集合求交集

既然可以使用 redis,那我直接用 redis 的 set 来搞交集不就行了。这里写的是 Yii 2.0 框架调用 redis 的方法,其他框架大同小异这里就不赘述了(这年头不会有人不用框架开发吧?):

1
2
3
Yii::$app->redis_connection->sadd('redisarr1', ...$arr1);       // 设置集合arr1
Yii::$app->redis_connection->sadd('redisarr1', ...$arr2);       // 设置集合arr1
Yii::$app->redis_connection->sinter('redisarr1', 'redisarr2');  // 求两个集合的交集

该方法也挺简单,经测试性能有所提升。

PHP 优化方法

类型转换

不知道 PHP 的取交集方法 array_intersect() 是否对数组元素的类型存在影响,猜测如果使用整型作为键值的话是不是会更快一些,那么在取交集前可以先进行类型转换。

数组反转

对于 PHPer 来说,判断某一元素是否在数组中出现,通常会使用 in_array() 方法进行判断。数组较小时,性能问题可以忽略不计。但在遭遇大数组时,则可能回产生糟糕的性能问题。解决这个问题的通行做法是先使用 array_flip() 将数组的 key-value 进行反转,然后再使用 isset() 方法进行判断。

从这个思路出发,我琢磨着是不是取交集也可以使用类似的方法进行处理,直接对数组键名而不是键值进行取交集操作。反正也就是先反转一下数组而已:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
<?php
function array_intersect(...$arrays)
{
    $flip_arrays = [];
    foreach ($arrays as $arr) {
        $flip_arrays[] = array_flip($arr);
    }

    $result = array_intersect_key(...$flip_arrays);

    return array_flip($result);
}

性能测试

测试原理

测试中直接生成大小为 100w 的随机数字数组。分别测试四种取交集方法:

  1. PHP 原生方法 array_intersect() 对整型数组取交集
  2. PHP 原生方法 array_intersect() 对字符串数组取交集
  3. 先 array_flip() 反转数组的 key-value,再对反转后的数组键名使用 array_intersect_key() 取交集
  4. edis 的 set 取交集
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<?php
Class IntersectTest {
    static $time = null;

    public function actionTest()
    {
        $n = 1000000;
        $arr1 = [];
        $arr2 = [];
        for ($i=1; $i <= $n; $i++) {
            $number = rand(1, 30000);
            $arr1[] = $number;
            $arr2[] = $number;
            $arr3[] = (string)$number;
            $arr4[] = (string)$number;
        }
        Yii::$app->redis_connection->sadd('redisIntarr1', ...$arr1);
        Yii::$app->redis_connection->sadd('redisIntarr2', ...$arr2);

        Yii::$app->redis_connection->sadd('redisStringarr1', ...$arr3);
        Yii::$app->redis_connection->sadd('redisStringarr2', ...$arr4);

        print_r('PHP version: ' . phpversion() . PHP_EOL);
        print_r('Tets sample count: ' . $n . PHP_EOL);
        self::infoTime('Test begin');
        $ret1 = array_intersect($arr1, $arr2);
        self::infoTime('PHP int array_intersect');
        $ret2 = array_intersect($arr3, $arr4);
        self::infoTime('PHP string array_intersect');
        $ret3 = self::array_intersect($arr1, $arr2);
        self::infoTime('PHP int array_flip & array_intersect');
        $ret4 = self::array_intersect($arr3, $arr4);
        self::infoTime('PHP string array_flip & array_intersect');
        $ret5 = Yii::$app->redis_connection->sinter('redisIntarr1', 'redisIntarr2');
        self::infoTime('redis int array_intersect');
        $ret6 = Yii::$app->redis_connection->sinter('redisStringarr1', 'redisStringarr2');
        self::infoTime('redis string array_intersect');
    }

    /**
     * 魔改的数组取交集方法
     * @param ...$arrays
     * @return int[]|string[]
     */
    public static function array_intersect(...$arrays)
    {
        $flip_arrays = [];
        foreach ($arrays as $arr) {
            $flip_arrays[] = array_flip($arr);
        }

        $result = array_intersect_key(...$flip_arrays);

        return array_flip($result);
    }

    public static function infoTime($info) {
        if (self::$time === null) {
            self::$time = microtime(true);
        }
        print_r('exeTime=' . self::getExecuteTime() .' ' . $info . PHP_EOL);
    }

    public static function getExecuteTime() {
        $now = microtime(true);
        if (self::$time === null) {
            self::$time = $now;
        }

        $executeTime = $now - self::$time;
        self::$time = $now;
        return round($executeTime,3);
    }
}

测试结果

PHP version: 7.3.6
Tets sample count: 20000
exeTime=0 Test begin
exeTime=0.043 PHP int array_intersect
exeTime=0.019 PHP string array_intersect
exeTime=0.002 PHP int array_flip & array_intersect
exeTime=0.002 PHP string array_flip & array_intersect
exeTime=0.118 redis int array_intersect
exeTime=0.117 redis string array_intersect


PHP version: 7.3.6
Tets sample count: 1000000
exeTime=0 Test begin
exeTime=2.874 PHP int array_intersect
exeTime=2.164 PHP string array_intersect
exeTime=0.038 PHP int array_flip & array_intersect
exeTime=0.077 PHP string array_flip & array_intersect
exeTime=0.119 redis int array_intersect
exeTime=0.119 redis string array_intersect
  • 从上述测试结果来看,如果按文首所述的场景,直接使用原生方法进行实现的接口响应耗时 17-21s (单次交集操作 0.043s)
    使用魔改方法优化后的接口响应耗时 0.8-1s (单次交集操作 0.002s)
  • 如果数组大小为 100w 级,那么性能问题将会被放大,差异大概是两个数量级的样子,也难怪 PHP 是世界上最好的语言。
  • 从测试结果来看 redis 的集合取交集性能表现也还是不错的,普通的 web 场景足够应付。吊诡的是不同数量级大小的数组居然对其性能没有影响,这里猜测这个耗时可能主要被建立 redis 连接的过程给占用了。

结论

  1. PHP 自带的 array_intersect() 方法只适合交集数组长度比较小的场景(看起来最好控制在 1k 以内),否则性能爆炸烂
  2. 如果需要对大数组进行交集操作,可以考虑使用魔改的 array_intersect() 方法,先 array_flip() 反转数组的键值,然后使用 array_intersect_key() 去交集,这样会快至少三个数量级。
  3. 不同数据类型的元素确实会对 PHP 原生方法的数组取交集性能产生影响,字符串类型的元素取交集性能更好。
  4. redis 的交集操作也挺好用,在上述方法不可使用的情况下,可以考虑使用 redis 进行交集操作。

后话

这个优化过程其实带出了几个值得思考的问题:

  1. 为什么 PHP 判断元素存在时,使用键名判断比使用键值判断性能更好?
  2. PHP 数组取交集的性能问题是否也是因为上述原因导致?
  3. 为什么使用 PHP 原生方法取交集时,数组元素为字符串型 比 数组元素为整型 的性能更好?
  4. redis 的取交集操作性能可以有多好?百万级大小的数组在 redis 取交集时,实际性能如何? 这些问题就暂时不在这篇水文内展开了。
updatedupdated2021-09-112021-09-11