在一个非常紧密的循环中,我需要访问一个包含数百万个元素的数组中的数万个值。键可以是未定义的:在这种情况下,它应该是法律的返回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中进行两次查找:一次用于检查存在性,另一次用于检索值。这有效地使运行时间加倍。
- 第二个使用错误抑制操作符,因此在该线路上创建了大量开销。
- 第三个调用错误处理程序(将检查error_reporting设置,然后不显示任何内容),从而创建开销。
我是否错过了一种避免错误处理的方法,但却可以使用单个Btree查找?
回答一些问题:
数组缓存复杂计算的结果-复杂到真实的时间。在数十亿可能的值中,只有数百万个产生有效的结果。数组看起来像1234567 => 23457,1234999 => 74361,.这被保存到几兆字节的PHP文件中,和include_once-d。初始加载时间无关紧要。
如果没有找到键,这仅仅意味着这个特定的值将不会返回有效的结果。麻烦的是每秒50 k+完成此操作。
8条答案
按热度按时间7eumitmz1#
更新
从PHP 7开始,你可以用null coalesce operator来完成这个任务:
字符串
旧答案
首先,数组不是B树,它是一个哈希表;一个桶数组(通过哈希函数索引),每个桶都有一个实际值的链表(在哈希冲突的情况下)。这意味着查找时间取决于哈希函数在桶中“传播”值的程度,即哈希冲突的数量是一个重要因素。
从技术上讲,这句话是最正确的:
型
这引入了一个函数调用,因此比优化后的
isset()
慢了 * 很多 *。慢了多少?~ 2 e3倍。接下来是使用引用来避免第二次查找:
型
不幸的是,如果
$lookup_table
数组中的元素不存在,那么这会修改$lookup_table
数组中的元素,因为PHP总是将引用设置为有效。这就剩下下面的方法了,它很像你自己的方法:
型
除了没有引用的副作用之外,它在运行时也更快,即使执行两次查找。
您可以考虑将数组划分为更小的部分,作为减少长查找时间的一种方法。
njthzxwz2#
我用下面的代码做了一些基准测试:
字符串
我发现运行速度最快的测试是使用
isset($array[$key]) ? $array[$key] : null
的测试,紧随其后的是仅禁用错误报告的解决方案。pcrecxhr3#
这个工作对我来说
字符串
但这也太快了
型
jdgnovmf4#
对此有两种典型的方法。
1.为未定义的键定义默认值。
1.检查未定义的键。
下面是如何执行第一个和尽可能少的代码。
字符串
下面是如何执行第二个。
型
tcomlyy65#
这只是一个突然的想法,需要测试,但你有没有尝试使用
array_intersect_key()
来获取现有的值,并使用array_merge来填充其余的值?它将消除访问数据的循环的需要。类似于这样的:字符串
请注意,我没有尝试它的性能明智的。
iyr7buue6#
@ operator和error_reporting方法都比使用isset慢。使用这两种方法,它修改了PHP的错误报告设置,但PHP的错误处理程序仍然会被调用。错误处理程序将检查error_reporting设置并退出而不报告任何内容,但这仍然需要时间。
ioekq8ef7#
我更喜欢使用
isset
函数,而不是逃避错误。我做了一个函数来检查键是否存在,如果不存在则返回默认值,在嵌套数组的情况下,你只需要按顺序添加其他键:嵌套数组查找:
字符串
使用示例:
型
逃避错误:
型
tct7dpnv8#
首先,通过保存一个新数组来重新组织数据以提高性能,其中数据按键排序,但新数组包含一个常规的数字索引。
这一部分将是耗时的,但只做一次。
字符串
一旦这样做了,它应该很快找到使用Binary Search的关键。以后你可以使用这样的函数。
型
要搜索一个键,你可以这样做。
型
如果
count($data)
一直在执行,那么可以将其缓存到存储数组数据的文件中。我怀疑这种方法在性能上会比对
$data
重复的常规线性搜索快得多。我不能保证它更快。只有八叉树会更快,但是构建八叉树的时间可能会抵消搜索性能(我以前经历过)。这取决于你必须在数据中进行多少搜索。