in_array 函数

大部分小伙伴第一时间想到的答案就是:in_array 函数啦,是吧,这是PHP内置的函数,可以判断字符串是否在数组中:

<?php
$arr = ['str1', 'str2', 'str3'];
var_dump('str4', $arr);

但是吧,这种写法效率不高,特别是数组中元素非常多的时候。TA的时间复杂度取决于数组的长度,也就是N。

isset 方法

$arr = ['str1', 'str2', 'str3'];
$arr = array_flip($arr);
var_dump(isset($arr['str4']));

首先,我们利用 array_flip 函数将数组的键值对颠倒,然后直接 isset 判断数组是否这个键存在。这样,时间复杂度直接变为O(1)了。

下面,我们做个测试:

<?php

$i = 200000;

$arr = [];
while ($i > 0) {
    $arr[] = uniqid();
    $i--;
}

$str = [
    'ha1',
    'sks',
    'dudu',
    'baidu',
    'qq',
];

$s = microtime(true);
foreach ($str as $i) {
    var_dump(in_array($i, $arr));
}
$e = microtime(true);
var_dump($s, $e, $e - $s);


$s = microtime(true);
$arr = array_flip($arr);
$flip = microtime(true);
foreach ($str as $i) {
    var_dump(isset($arr[$i]));
}
$e = microtime(true);
var_dump($s, $flip, $e, $e - $s);

输出结果:

# 第一种
bool(false)
bool(false)
bool(false)
bool(false)
bool(false)
float(1591847955.7787)
float(1591847955.791)
float(0.012239933013916)

# 第二种
bool(false)
bool(false)
bool(false)
bool(false)
bool(false)
float(1591847955.791)
float(1591847955.8055)
float(1591847955.8055)
float(0.014477968215942)

从结果可以看到,第一种的效率比先翻转在判断的第二种方法要好一点。这样的结果也意味着,如果你要判断字符串是否存在一个数组中,还是用PHP自带的 in_array 函数较好。

从第二种的输出结果可以看到,几乎所有的时间都用来进行数组的flip了,而判断是否存在几乎没有时间损耗。但这并不意味着第二种方法不可取。如果事先在创建 $arr 数组的时候直接将值作为数组的键存储,那么肯定是第二种方法优于 in_array 函数。就像下面这样:

<?php

$i = 200000;

$arr = [];
while ($i > 0) {
    $arr[uniqid()] = 1;
    $i--;
}

$str = [
    'ha1',
    'sks',
    'dudu',
    'baidu',
    'qq',
];

$s = microtime(true);
foreach ($str as $i) {
    var_dump(isset($i, $arr));
}
$e = microtime(true);
var_dump($s, $e);

输出结果:

bool(true)
bool(true)
bool(true)
bool(true)
bool(true)
float(1591849858.1098)
float(1591849858.1098)