PHP中in_array()的性能很差。搜索数组中特定值的最快方法是什么？

Question

我有以下简单的代码用于测试创建主键时的冲突：

$machine_ids = array();

for($i = 0; $i < 100000; $i++) {
    //Generate machine id returns a 15 character alphanumeric string
    $mid = Functions::generate_machine_id();

    if(in_array($mid, $machine_ids)) {
        die("Collision!");
    } else {
        $machine_ids[] = $mid;  
    }
}

die("Success!");

任何想法为什么运行需要花费多分钟？有没有办法加快速度？

- Justin

---

你已经调试过了，in_array 才是罪魁祸首，而不是 Functions::generate_machine_id() 吗？ - deceze

你手头有 Functions::generate_machine_id 的代码吗？ - cHao

Answer 1

for($i = 0; $i < 100000; $i++) 
{
  //Generate machine id returns a 15 character alphanumeric string
  $mid = Functions::generate_machine_id();
  if (isset($machine_ids[$mid]))
  {
    die("Collision!");
  }
  $machine_ids[$mid] = true;
}

- ajreal

Answer 2

为此，使用$mid作为键，使用虚拟值作为值。具体来说，不要使用

if(in_array($mid, $machine_ids)) {
    die("Collision!");
} else {
    $machine_ids[] = $mid;  
}

使用

if(isset($machine_ids[$mid])) {
    die("Collision!");
} else {
    $machine_ids[$mid] = 1;  
}

最后，您可以使用array_keys($machine_ids)提取最初想要的数组。

这应该会更快。如果仍然慢，那么您的Functions::generate_machine_id()函数很可能是慢的。

编辑根据评论添加isset。

- Amadan

---

赶我抢了言。 :) 不过你应该使用isset($machine_ids[$mid])。 - deceze

同意deceze的观点，我认为如果$machine_ids[$mid]的值是整数0、空字符串、NULL等，则会返回false（实际上不是冲突）。无论如何，使用isset()是最好的选择。然而，我刚刚注意到OP说它始终是一个15个字符的字母数字组合。 - Wesley Murch

@deceze：有什么原因吗？isset的性能损失是否比隐式转换为布尔值的性能损失更低？还是说这只是理论上的问题 - 因为在PHP中，0也是false，这与isset不同？（在这种情况下，我们只有空值和1，所以很安全） - Amadan

@Amadan：当$machine_ids[$mid]未定义时，它还会生成一个通知。 - Wesley Murch

我明白了。我不知道那个。已经有一段时间我没有经常使用PHP了 :) - Amadan

Answer 3

检查数组成员是一项O(n)操作，因为您必须将值与数组中的每个元素进行比较。当您向数组添加大量内容后，自然会变得更慢。

如果您需要执行大量成员测试，就像这里的情况一样，您应该使用支持O(1)成员测试的不同数据结构，例如哈希表。

- verdesmarald

Answer 4

重构您的代码，使用关联数组来保存机器ID，并使用 isset 检查。

if( isset($machine_id[$mid]) ) die("Collision");

$machine_ids[$mid] = $mid;

使用isset应该更快

- Jay Sidri

Answer 5

如果您需要最佳性能，您需要将数据存储为数组键，并使用isset或array_key_exists（自php >= 7.4以来，array_key_exists与isset一样快）而不是使用in_array。

注意。在哈希映射上使用isset比在数组中搜索值（in_array）更快确实是正确的，但请记住，将值数组["foo", "bar", "baz"]转换为哈希映射["foo" => true, "bar" => true, "baz" => true]会产生内存成本（以及可能构建哈希映射，这取决于您何时以及如何进行操作）。像所有事物一样，您必须权衡每种情况的利弊，确定哈希映射或值数组（列表）对您的需求最有效。这不仅适用于PHP，而且是计算机科学的一个通用问题领域。

以下是一些来自https://gist.github.com/alcaeus/536156663fac96744eba77b3e133e50a的性能测试。

<?php declare(strict_types = 1);

function testPerformance($name, Closure $closure, $runs = 1000000)
{
    $start = microtime(true);
    for (; $runs > 0; $runs--)
    {
        $closure();
    }
    $end = microtime(true);

    printf("Function call %s took %.5f seconds\n", $name, $end - $start);
}

$items = [1111111];
for ($i = 0; $i < 100000; $i++) {
    $items[] = rand(0, 1000000);
}
$items = array_unique($items);
shuffle($items);

$assocItems = array_combine($items, array_fill(0, count($items), true));

$in_array = function () use ($items) {
    in_array(1111111, $items);
};

$isset = function () use ($assocItems) {
    isset($items[1111111]);
};

$array_key_exists = function () use ($assocItems) {
    array_key_exists(1111111, $assocItems);
};

testPerformance('in_array', $in_array, 100000);
testPerformance('isset', $isset, 100000);
testPerformance('array_key_exists', $array_key_exists, 100000);

输出：

Function call in_array took 5.01030 seconds
Function call isset took 0.00627 seconds
Function call array_key_exists took 0.00620 seconds

- Arsen