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

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

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

场景描述

接口输出一个简单的 list 接口，大概 100+ 行数据，每行数据有 4 个字段都需要进行交集操作。即该接口总共需要进行 400-500 次交集操作。
进行交集操作的成员数组数据量大概在 2w 左右，全部为数值（类型不敏感，可根据需要转换为 string / int 类型）
可以使用 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');  // 求两个集合的交集

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

 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 的随机数字数组。分别测试四种取交集方法：

PHP 原生方法 array_intersect() 对整型数组取交集
PHP 原生方法 array_intersect() 对字符串数组取交集
先 array_flip() 反转数组的 key-value，再对反转后的数组键名使用 array_intersect_key() 取交集
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 连接的过程给占用了。

结论

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

后话

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

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

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

场景描述

实现路径

PHP 原生方法

Redis 集合求交集

PHP 优化方法

类型转换

数组反转

性能测试

测试原理

测试结果

结论

后话

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

相关文章：