PHP：处理未定义数组键的最快方法

php performance

2022-08-30 08:47:19

在一个非常紧凑的循环中，我需要访问包含数百万个元素的数组中的数万个值。密钥可以未定义：在这种情况下，返回 NULL 而不显示任何错误消息是合法的：

数组键存在：元素的返回值。数组键不存在：返回 null。

我知道多种解决方案：

    if (isset($lookup_table[$key])) {
        return $lookup_table[$key];
    } else {
        return;
    }

或

@return $lookup_table[$key];

或

error_reporting(0);
$return = $lookup_table[$key];
error_reporting(E_ALL);
return $return;

所有解决方案都远非最佳：

第一个需要在 B-TREE 中查找 2 个：一个用于检查是否存在，另一个用于检索值。这有效地使运行时加倍。
第二个使用错误抑制运算符，因此在该线路上产生巨大的开销。
第三个调用错误处理程序（将检查error_reporting设置，然后不显示任何内容），从而产生开销。

我的问题是，如果我错过了一种避免错误处理的方法，但却使用单个Btree查找？

要回答一些问题：

数组缓存复杂计算的结果 - 复杂计算以实时完成。在数十亿个可能的值中，只有数百万个产生有效的结果。数组看起来像 1234567 => 23457， 1234999 => 74361， ....它被保存到几兆字节的PHP文件中，并在执行开始时include_once-d。初始加载时间无关紧要。如果未找到该键，则仅表示此特定值不会返回有效结果。麻烦的是每秒50k +完成此操作。

结论

由于无法通过单个查找和错误处理来获取值，因此我很难接受单个答案。相反，我投票支持所有伟大的贡献。

最有价值的输入，其中：

使用array_key_exists，因为它比替代品更快
查看 PHP 的 QuickHash

关于PHP如何处理数组有很多困惑。如果检查源代码，您将看到所有数组都是平衡树。构建自己的查找方法在C和C++中很常见，但在PHP等高级脚本语言中不具有性能。

答案 1

更新

从 PHP 7 开始，您可以使用 null 合并运算符完成此操作：

return $table[$key] ?? null;

旧答案

首先，数组不是作为B树实现的，它是一个哈希表;一个存储桶数组（通过哈希函数编制索引），每个存储桶都有一个实际值的链接列表（在哈希冲突的情况下）。这意味着查找时间取决于哈希函数在存储桶中“传播”值的程度，即哈希冲突的次数是一个重要因素。

从技术上讲，这种说法是最正确的：

return array_key_exists($key, $table) ? $table[$key] : null;

这引入了一个函数调用，因此比优化的慢得多。多少？慢约 2e3 倍。isset()

接下来是使用引用来避免第二次查找：

$tmp = &$lookup_table[$key];

return isset($tmp) ? $tmp : null;

不幸的是，如果该项不存在，这将修改原始数组，因为 PHP 始终使引用有效。$lookup_table

这就剩下以下方法，它与您自己的方法非常相似：

return isset($lookup_table[$key]) ? $lookup_table[$key] : null;

除了没有引用的副作用外，即使在执行两次查找时，它在运行时也更快。

您可以考虑将数组划分为更小的部分，作为减少长时间查找时间的一种方法。

答案 2

我用下面的代码做了一些基准标记：

set_time_limit(100);

$count = 2500000;
$search_index_end = $count * 1.5;
$search_index_start = $count * .5;

$array = array();
for ($i = 0; $i < $count; $i++)
    $array[md5($i)] = $i;

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = isset($array[$key]) ? $array[$key] : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = array_key_exists($key, $array) ? $array[$key] : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";


$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = @$array[$key];
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

$error_reporting = error_reporting();
error_reporting(0);
$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $test = $array[$key];
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";
error_reporting($error_reporting);

$start = microtime(true);
for ($i = $search_index_start; $i < $search_index_end; $i++) {
    $key = md5($i);
    $tmp = &$array[$key];
    $test = isset($tmp) ? $tmp : null;
}
$end = microtime(true);
echo ($end - $start) . " seconds<br/>";

我发现运行最快的测试是使用紧随解决方案的测试，该解决方案只是禁用错误报告。isset($array[$key]) ? $array[$key] : null