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!");

知道为什么这需要很多分钟才能运行吗？无论如何要加快速度吗？

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;
}

Answer 2

为此，使用 $mid 作为键，使用虚拟值作为值。具体来说，您可以使用 array_keys($machine_ids) 来提取您最初想要的数组，而不是

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

使用

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

最后。

这应该快得多。如果仍然很慢，那么您的 Functions::generate_machine_id() 很慢。

已编辑根据评论添加isset。

Answer 3

检查数组成员资格是一个 O(n) 操作，因为您必须将该值与数组中的每个元素进行比较。当你向数组添加一大堆东西后，它自然会变慢。

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

Answer 4

重构您的代码，以便它使用关联的数组来保存机器 ID 并使用 isset 进行检查

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

$machine_ids[$mid] = $mid;

使用 isset 应该更快

Answer 5

如果您需要为您的情况提供最佳性能，则需要将数据存储为数组键并
使用 isset 或 array_key_exists（因为 php >= 7.4 array_key_exists 现在与 isset< /em>) 而不是 in_array。

注意。确实，哈希映射上的 isset 比在数组中搜索值 (in_array) 更快，但请记住
将值数组 ["foo", "bar", "baz"] 转换为哈希值
地图，[“foo”=>正确，“栏”=>正确，“baz”=> true]，产生记忆
成本（以及可能构建哈希图，具体取决于
如何以及何时进行）。与所有事情一样，你必须权衡
优点与优点每种情况下的 cons 来确定是哈希映射还是数组（列表）
的价值观最适合您的需求。这不是特定于 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