PHP源码阅读in_array

发表于

in_array

函数搜索数组中是否存在指定的值。存在，返回true；否，返回false。

时间复杂度

最差是O(n)，平均O(n/2)

源码

只拿一个分支出来看，其他的差不多，从源码中的ZEND_HASH_FOREACH_KEY_VAL，可以看出实现方式，是遍历数组，搜索是否存在这个值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
	if (fast_equal_check_long(value, entry)) {
		if (behavior == 0) {
			RETURN_TRUE;
		} else {
			if (str_idx) {
				RETVAL_STR_COPY(str_idx);
			} else {
				RETVAL_LONG(num_idx);
			}
			return;
		}
	}
} ZEND_HASH_FOREACH_END();

优化

网上有人给出两种优化方法。第一种，使用 array_flip key-value翻转，通过isset（或者array_key_exists）判断是否存在；第二种，通过implode把数组合并成一个字符串，再通过strpos搜索。对于这两种优化，我是持有怀疑态度的。下面一一来试验一番。

先看in_array耗时，经过多次测试，耗时100w整型在30ms左右：

1
2
3
4
5
6
7
8
9
10
ini_set('memory_limit', '2048M');
$arr = range(0,10000000,1);
echo get_millisecond().' ms'.PHP_EOL;
var_dump(in_array(10000000, $arr));
echo get_millisecond().' ms'.PHP_EOL;
// 1499311572333 ms
// bool(true)
// 1499311572363 ms

第一种，先翻转，再isset；经过多次测试，耗时100w整型在200ms左右：

1
2
3
4
5
6
7
8
9
10
11
ini_set('memory_limit', '2048M');
$arr = range(0,10000000,1);
echo get_millisecond().' ms'.PHP_EOL;
$new_arr = array_flip($arr);
var_dump(isset($new_arr[10000000]));
echo get_millisecond().' ms'.PHP_EOL;
// 1499311825323 ms
// bool(true)
// 1499311825563 ms

第二种，先implode成一个字符串，再strpos搜索；经过多次测试，耗时100w整型在400ms左右：

1
2
3
4
5
6
7
8
9
10
11
12
ini_set('memory_limit', '2048M');
$arr = range(0,10000000,1);
echo get_millisecond().' ms'.PHP_EOL;
$s = implode('_', $arr);
$s = '_'.$s.'_';
var_dump(strpos($s, '_10000000_'));
echo get_millisecond().' ms'.PHP_EOL;
// 1499312200167 ms
// int(78888890)
// 1499312200624 ms

优化总结

第一种，iseet，hash表的查找，在良好的hash算法下，时间复杂度可以达到O(1)，但不要忘记了，在isset前还有个，array_flip操作，这个的时间复杂度是也O(n)，还需要付出额外的内存空间，毕竟生成了一个新的数组。

第二种，strpos php底层的实现是KMP算法，时间复杂度是O(n+m)，而且还有implode的操作，最后还会生成一个字符串，也需要付出额外的内存空间。

那么，是否in_array就已经没法优化了呢，其实也不然，这个的优化不能撇开使用场景。如果是需要频繁搜索的，可以一开始就构建一个集合，例如：array(search => true)，这样可以直接用isset；如果是需要一个有序数组，那么一开始就构建成有序数组，array(0,1,2,3)，搜索可以用上搜索算法，快排等。