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

idv4meu8  于 2022-12-21  发布在  PHP
关注(0)|答案(8)|浏览(418)

在一个非常紧密的循环中,我需要访问包含数百万个元素的数组中的数万个值。键可以是未定义的:在这种情况下,应法律的返回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树中进行2次查找:一个检查存在性,另一个检索值,这实际上使运行时间加倍。
  • 第二种方法使用错误抑制操作符,因此在该行上产生了大量开销。
  • 第三种方法调用错误处理程序(它将检查error_reporting设置,然后不显示任何内容),从而产生开销。
    我的问题是,我是否错过了避免错误处理的方法,但仍然使用单个Btree查找?

要回答一些问题:

该数组缓存复杂计算的结果-复杂到无法真实的完成。在数十亿个可能的值中,只有数百万个值产生有效的结果。该数组看起来像1234567 =〉23457,1234999 =〉74361,...。该数组保存到几兆字节的PHP文件中,并在执行开始时使用include_once-d。初始加载时间并不重要。如果没有找到键,这仅仅意味着这个特定的值将不会返回有效的结果。麻烦的是每秒要完成50 k+。

结论

编辑:已过时,请检查已接受的答案。

由于没有办法通过一次查找而不进行错误处理来获得值,所以我很难接受一个单一的答案,相反,我对所有重要的贡献都投了赞成票。
最有价值的输入包括:

  • 使用array_key_exists,因为它比其他方法快
  • 查看PHP的QuickHash

PHP处理数组的方式有很多困惑。如果你检查源代码,你会发现所有的数组都是平衡树。构建自己的查找方法在C和C++中很常见,但在PHP这样的高级脚本语言中却不常见。

djmepvbi

djmepvbi1#

更新

从PHP 7开始,您可以使用null coalesce operator

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;

除了没有引用的副作用外,它在运行时也更快,即使执行两次查找也是如此。
您可以考虑将数组划分为更小的部分,作为减少较长查找时间的一种方法。

f0ofjuux

f0ofjuux2#

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

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

kadbb459

kadbb4593#

这对我有用

{{ isset($array['key']) ? $array['key']: 'Default' }}

但这太快了

{{ $array['key'] or 'Default' }}
r7s23pms

r7s23pms4#

对此有两种典型的方法。
1.为未定义的键定义默认值。
1.检查未定义的键。
下面介绍如何执行第一个代码,并且代码越少越好。

$data = array_merge(array($key=>false),$data);
return $data[$key];

下面是如何执行第二个。

return isset($data[$key]) ? $data[$key] : false;
wrrgggsh

wrrgggsh5#

这只是一个需要测试的突发想法,但是您是否尝试过使用array_intersect_key()来获取现有值,并使用array_merge来填充其余值?它将消除访问数据的循环需求,类似于以下内容:

$searched_keys = array ('key1' => null, 'key2' => null); // the list of the keys to find

$exiting_values = array_intersect_key($lookup_table, $searched_keys);
$all_values = array_merge($searched_keys, $exiting_keys);

请注意,我没有尝试它的性能明智的。

rjjhvcjd

rjjhvcjd6#

@ operator和error_reporting方法都比使用isset慢。使用这两种方法,它修改了PHP的错误报告设置,但PHP的错误处理程序仍将被调用。错误处理程序将检查error_reporting设置,并在不报告任何内容的情况下退出,但这仍然需要时间。

zbdgwd5y

zbdgwd5y7#

我更喜欢使用isset函数而不是转义错误。我创建了一个函数来检查键是否存在,如果不存在,则返回默认值,在嵌套数组的情况下,您只需要按顺序添加其他键:
嵌套数组查找:

/**
 * Lookup array value.
 *
 * @param array $array
 * @param array $keys
 * @param $defaultValue
 */
public static function array_key_lookup($array, $keys, $defaultValue)
{
    $value = $array;
    foreach ($keys as $key) {
        if (isset($value[$key])) {
            $value = $value[$key];
        } else {
            $value = $defaultValue;
            break;
        }
    }

    return $value;
}

用法示例:

$array = [
    'key1' => 'value1',
    'key2' => 'value2',
    'key3' => [
        'key3a' => 'value3a',
        'key3b' => 'value3b'
    ]
];

array_key_lookup($array, ['key3', 'key3a'], 'default')
'value3a'

array_key_lookup($array, ['key2', 'key2a'], 'default')
'default'

array_key_lookup($array, ['key2'], 'default')
'value2'

array_key_lookup($array, ['key5'], 'default')
'default'

避免错误:

$value = @$array[$key1][$key2] ?: $defaultValue;
lnlaulya

lnlaulya8#

首先,重新组织数据以提高性能,方法是保存一个新数组,其中的数据按键排序,但新数组包含一个常规的数字索引。
这部分将是耗时的,但只做一次。

// first sort the array by it's keys
 ksort($data);

 // second create a new array with numeric index
 $tmp = new array();
 foreach($data as $key=>$value)
 {
    $tmp[] = array('key'=>$key,'value'=>$value);
 }
 // now save and use this data instead
 save_to_file($tmp);

完成后,使用Binary Search可以很快找到密钥。稍后您可以使用这样的函数。

function findKey($key, $data, $start, $end)
  { 
    if($end < $start) 
    { 
        return null; 
    } 

    $mid = (int)(($end - $start) / 2) + $start; 

    if($data[$mid]['key'] > $key) 
    { 
        return findKey($key, $data, $start, $mid - 1); 
    } 
    else if($data[$mid]['key'] < $key) 
    { 
        return findKey($key, $data, $mid + 1, $end); 
    } 

    return $data[$mid]['value'];
 }

要执行对键的搜索,可以执行以下操作。

$result = findKey($key, $data, 0, count($data));
 if($result === null)
 {
      // key not found.
 }

如果count($data)一直在执行,那么可以将其缓存在存储数组数据的文件中。
我怀疑这种方法在性能上会比对$data重复的常规线性搜索快得多。我不能保证它更快。只有八叉树会更快,但构建八叉树的时间可能会抵消搜索性能(我以前经历过)。这取决于你必须在数据中做多少搜索。

相关问题