2021-06-09

PHP

判断元素是否在数组内的几种方法对比

数组是很常用的一个数据结构，而且经常需要判断某个元素是否在数组中，这在PHP中有很多种方法，有：

foreach循环遍历数据
in_array()
array_search()
isset()
array_key_exists()

还有其他方法，这里就不说了。我们在网上搜索相关问题基本都是清一色的教我们如何使用in_array()函数，好像PHP中判断数组包含某个元素只有这一种方式似的，这次本文就来分析下除foreach外其他四种方式的执行效率。

具体四种函数如何使用就不多介绍了，我想看我文章的都不是LV1级别的吧，如果不懂请自行查阅php.net网站。

测试方法

随机生成一个大数组，然后任取一些元素分别调用上面的几个函数判断是否在生成的大数组内，记录下运行时消耗的最大内存和执行时间。

测试环境

PHP 7.2.34 (cli) (built: Mar 14 2021 18:35:27) ( NTS )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.2.0, Copyright (c) 1998-2018 Zend Technologies
    with Zend OPcache v7.2.34, Copyright (c) 1999-2018, by Zend Technologie

测试代码

下面函数创建随机字符的数组：

function random_str( $cnt = 1000, $length = 8 ) {
    $chars = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
    'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
    'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
    'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y','Z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!',
    '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '_',
    '[', ']', '{', '}', '<', '>', '~', '`', '+', '=', ',',
    '.', ';', ':', '/', '?', '|');
    $a = [];

    for($j = 0; $j < $cnt; ++$j) {
        $keys = array_rand($chars, $length);
        $p = '';
        for($i = 0; $i < $length; $i++) {
            $p .= $chars[$keys[$i]];
        }

        $a[] = $p;
    }

    return $a;
}

最大内存使用情况：

function get_memory() {
	$size = memory_get_peak_usage(true);
    $mod = 1024;
    $units = array('B', 'Kb', 'Mb', 'Gb');
    $format = '%.2f%s';

    for ($i = 0; $size > $mod; $i++) {
        $size /= $mod;
    }

    return sprintf($format, round($size, 3), $units[$i]);
}

具体的测试代码大致这样：

// 创建大小为10w的数组
$arr = random_str(100000);
$cnt = count($arr);

// 取1个出来判断
$search_arr = [];
for ($i=0; $i<1; ++$i) {
    $r = rand(0, $cnt-1);
    $search_arr[] = $arr[$r];
}

echo "----------- in_array -----------" . PHP_EOL;
$t0 = microtime(true);
for ($i=0; $i < 1; ++$i) {
    if (in_array($search_arr[$i], $arr)) {
        echo "";
    }
}

echo "memory: " . get_memory() . PHP_EOL;
echo "time elapsed: " . (microtime(true) - $t0) . PHP_EOL;

上面是创建10w大小数组，取一个用in_array()来判断，同样地，其他的几个函数，把in_array()改一下就行，但是要注意的是：

isset()和array_key_exists()使用数组的key来判断，所以需要多一步：将创建的数组的key和value用array_flip()对调一下，这一步也是要加入到统计中去的。

代码如下：

echo "----------- array_key_exists -----------" . PHP_EOL;
$t4 = microtime(true);
$key_arr = array_flip($arr);
echo "array_flip time elapsed : " . (microtime(true) - $t4) . PHP_EOL;
for ($i=0; $i<1; ++$i) {
   if (array_key_exists($search_arr[$i], $key_arr)) {
        echo "" ;
    }
}

echo "memory: " . get_memory() . PHP_EOL;
echo "time elapsed: " . (microtime(true) - $t4) . PHP_EOL;

isset()函数也是类似。

测试结果如下：

17217

从图中可以看到，in_array和array_search遥遥领先与另外两个，当100w数据时，前两个的执行速度快了两个数量级。内存方面，isset和array_key_exists也是内存消耗大户，消耗的内存几乎是in_array和array_search的1.5倍。

仔细分析可以发现isset和array_key_exists其实并不慢，罪魁祸首是array_flip()，因为这两个函数都是通过key来判断的，所以我们需要把value转换成key，这就额外需要存储100w数据的空间，并且还要遍历把数据插入进去，可想而知是很耗内存和时间的。可以看如下截图：

17594

整个执行时间0.14150094985962，而array_flip()这个函数执行就花了0.1414098739624，isset和array_key_exists本身是很快的。

如果要判断多个元素呢？是不是会降低array_flip()函数带来的影响？我们继续测试。

测试100个元素：

17819

内存几乎没有变化，但执行时间in_array和array_search比后两个慢了几倍，变化的很明显，而isset和array_key_exists执行时间和查询2个元素几乎一致，查询的个数并不影响其效率，相反，in_array和array_search的执行效率和个数成正比。

再来测试1000个：

18040

在查询1000个的情况下，我等in_array和array_search这两个函数的结果已经不耐烦了，而isset和array_key_exists仍然很淡定，变化不大。

上面是对大字符串数组的测试，稍微做下调整来看看如果是连续的数字会是什么结果。

结果差不多，同样是查找1000个，array_key_exists()函数花费了0.028817176818848，in_array()函数仍然用了1.4303638935089。

为什么

那么为什么基于key的查询速度会快这么多呢？本着“不抛弃，不放弃”的原则，我查了下PHP中关于数组的实现，使用了HashTable。

18414

想必学校老师都已经教过吧（【算法与数据结构】复习起来），查找时通过hash函数计算元素索引，这个过程是很快的可以看作是常量O©的时间复杂度，所以就有了上面的测试结果，in_array()和array_search()在查找时需要遍历整个数组，时间复杂度是O(n)，这当然慢咯，而通过key查找只要执行hash函数定位到索引，这速度肯定不是一个量级的。当然，鱼和熊掌不能兼得，通过key查找首先需要构造这样的数组，势必会降低效率还要消耗很多内存。

总结

在数据量少的情况下，建议使用in_array和array_search速度够快而且内存占用少，数据量特别大的时候，可以用isset和array_key_exists，同时也要考虑下内存的占用。

参考

https://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions/2484455#2484455

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

欢迎阅读本篇文章，如有兴趣可以关注博主公众号哦：