PHP源码阅读in_array

发布于 2020-02-20  189 次阅读


in_array

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

时间复杂度

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

源码

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

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左右:

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左右:

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左右:

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),搜索可以用上搜索算法,快排等。


公交车司机终于在众人的指责中将座位让给了老太太