55

在一个非常紧凑的循环中，我需要访问包含数百万个元素的数组中的数万个值。键可以是未定义的：在这种情况下，返回 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 等高级脚本语言中性能不佳。

4

8 回答 8

79

更新

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

return $table[$key] ?? null;

旧答案

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

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

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

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

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

$tmp = &$lookup_table[$key];

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

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

这留下了以下方法，这很像您自己的方法：

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

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

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

于 2013-05-21T17:27:02.890 回答
4

我用以下代码做了一些基准测试：

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

于 2013-05-21T17:49:09.257 回答
1

有两种典型的方法。

  1. 为未定义的键定义默认值。
  2. 检查未定义的键。

以下是如何执行第一个和尽可能少的代码。

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

以下是如何执行第二个。

return isset($data[$key]) ? $data[$key] : false;
于 2013-05-21T17:22:34.927 回答
1

只是一个必须测试的突然想法，但是您是否尝试使用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);

请注意，我没有在性能方面尝试过。

于 2013-05-21T17:42:41.280 回答
1

为我工作 

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

但这很快

{{ $array['key'] or 'Default' }}
于 2016-01-25T00:06:58.340 回答
1

@ 运算符和 error_reporting 方法都比使用 isset 慢。使用这两种方法，它都会修改 PHP 的错误报告设置，但仍会调用 PHP 的错误处理程序。错误处理程序将检查 error_reporting 设置并退出而不报告任何内容，但这仍然需要时间。

于 2017-03-15T01:21:12.177 回答
1

我更喜欢使用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;
于 2019-10-11T15:00:29.797 回答
0

首先，通过保存一个新数组来重新组织数据以提高性能，其中数据按键排序，但新数组包含常规数字索引。

这部分会很耗时，但只完成一次。

 // 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. 我不能保证它会更快。只有八叉树会更快，但构建八叉树的时间可能会抵消搜索性能（我以前经历过）。这取决于您必须在数据中进行多少搜索。

于 2013-05-21T18:12:27.010 回答