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

Question

在一个非常紧凑的循环中,我需要访问包含数百万个元素的数组中的数万个值.密钥可以不确定:在这种情况下,返回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.初始加载时间无关紧要.如果未找到密钥,则仅表示此特定calue不会返回有效结果.麻烦的是每秒完成50k +.

结论

由于没有找到通过单个查找获得值并且没有错误处理的方法,我很难接受单个答案.相反,我赞成了所有伟大的贡献.

其中最有价值的输入: - 使用array_key_exists,因为它比替代品更快 - 查看php的QuickHash

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

Answer 1

更新

从PHP 7开始,您可以使用null coalesce运算符完成此操作:

return $table[$key] ?? null;

老答案

首先,数组不是作为B树实现的,它是一个哈希表; 一个桶数组(通过哈希函数索引),每个桶都有一个实际值的链表(如果是哈希冲突).这意味着查找时间取决于散列函数在桶中"扩展"值的程度,即散列冲突的数量是一个重要因素.

从技术上讲,这句话是最正确的:

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

这引入了函数调用,因此比优化的要慢得多isset().多少？〜2e3倍慢.

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

$tmp = &$lookup_table[$key];

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

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

这留下了以下方法,这与您自己的方法非常相似:

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

除了没有引用的副作用之外,它在运行时也更快,即使执行两次查找也是如此.

您可以考虑将数组划分为较小的部分,作为缓解长查找时间的一种方法.

Answer 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紧随其后使用仅禁用错误报告的解决方案的测试。