PHP函数的Big-O列表

在使用PHP一段时间后，我注意到并非所有内置PHP函数都像预期的那样快。考虑使用缓存的质数数组来判断一个数字是否是质数的函数的两种可能实现。

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
$result_array[$number] = in_array( $number, $large_prime_array );
}


//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) {
$result_array[$number] = array_key_exists( $number, $large_prime_array );
}

这是因为in_array是用线性搜索O(n)实现的，它将随着$prime_array的增长而线性地减慢。其中array_key_exists函数是通过哈希查找O(1)实现的，除非哈希表被大量填充(在这种情况下，它只有O(n))，否则哈希查找不会变慢。

到目前为止，我不得不通过反复试验来发现大o，偶尔也会发现查看源代码。现在问题来了……

是否有所有PHP内置函数的理论(或实际)大O时间列表?

*或者至少是有趣的

例如，我发现很难预测列出的函数的大O，因为可能的实现取决于PHP的未知核心数据结构:array_merge， array_merge_recursive， array_reverse， array_intersect， array_combine， str_replace(带有数组输入)等。

92647 次浏览
小开

对于您具体描述的情况的解释是，关联数组被实现为哈希表-因此按键查找(相应地，array_key_exists)是O(1)。但是，数组不是按值建立索引的，因此在一般情况下，发现数组中是否存在值的唯一方法是线性搜索。这没什么好惊讶的。

我不认为有关于PHP方法的算法复杂性的具体全面的文档。然而，如果它是一个足够大的问题，值得努力，你总是可以查看源代码。

小开

你几乎总是想使用isset而不是array_key_exists。我没有查看内部结构，但我非常确定array_key_exists是O(N)，因为它遍历数组的每个键，而isset尝试使用访问数组索引时使用的相同哈希算法访问元素。应该是O(1)

需要注意的一个“陷阱”是:

$search_array = array('first' => null, 'second' => 4);


// returns false
isset($search_array['first']);


// returns true
array_key_exists('first', $search_array);

我很好奇，所以我对差异进行了基准测试:

<?php


$bigArray = range(1,100000);


$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
isset($bigArray[50000]);
}


echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';


$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
array_key_exists(50000, $bigArray);
}


echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

is_set: 0.132308959961秒
array_key_exists: 2.33202195168 seconds

.

当然，这并没有显示时间复杂度，但它确实显示了两个函数之间的比较。

要测试时间复杂度，请比较在第一个键和最后一个键上运行其中一个函数所花费的时间。

小开
最佳答案

因为似乎没有人这样做之前，我认为这将是一个好主意，以供参考的地方。我已经通过基准测试或代码浏览来描述array_*函数。我试着把更有趣的Big-O放在顶部。这个列表并不完整。

注意:所有大O的计算假设哈希查找是O(1)，即使它实际上是O(n)。n的系数非常低，在查找Big-O的特性开始生效之前，存储足够大的数组的ram开销会对您造成伤害。例如，在N=1时调用array_key_exists和在N=1,000,000时调用array_key_exists之间的差异是大约50%的时间增加。

有趣的观点:

  1. isset/array_key_exists比in_array和array_search快得多
  2. +(union)比array_merge快一点(而且看起来更好)。但它的工作方式确实不同，所以要记住这一点。
  3. shuffle和array_rand在同一个大o层
  4. 由于重索引惩罚，array_pop/array_push比array_shift/array_unshift快

查找:

array_key_exists O(n)但非常接近O(1) -这是因为碰撞中的线性轮询，但由于碰撞的机会非常小，系数也非常小。我发现您将哈希查找视为O(1)，以给出更现实的大O。例如，N=1000和N=100000之间的差异仅为50%。

isset( $array[$index] ) O(n)但非常接近O(1) -它使用与array_key_exists相同的查找。由于它的语言结构，如果键是硬编码的，将缓存查找，从而在重复使用相同键的情况下加快速度。

in_array O(n) -这是因为它在数组中进行线性搜索，直到找到值。

array_search O(n) -它使用与in_array相同的核心函数，但返回值。

队列的函数:

array_push O(∑var_i, for all i)

array_pop O (1)

array_shift O(n) -它必须重新索引所有的键

array_unshift O(n +∑var_i, for all i) -它必须重新索引所有的键

数组交叉，并和，减法:

array_intersect_key如果交集100% do O(Max(param_i_size)*∑param_i_count, for all i)，如果交集0%相交O(∑param_i_size, for all i)

array_intersect如果交集100%做O(n²*∑param_i_count，对于所有i)，如果交集0%做O(n²)

array_intersect_assoc如果交集100% do O(Max(param_i_size)*∑param_i_count, for all i)，如果交集0%相交O(∑param_i_size, for all i)

array_diff O(π param_i_size, for all i) -这是所有param_size的乘积

array_diff_key O(∑param_i_size, for i != 1) -这是因为我们不需要遍历第一个数组。

array_merge O(∑array_i, i != 1) -不需要遍历第一个数组

+ (union) O(n)，其中n是第二个数组的大小(即array_first + array_second) -开销比array_merge少，因为它不需要重新编号

array_replace O(∑array_i, for all i)

随机:

shuffle O (n)

array_rand O(n) -需要线性轮询。

明显的大0:

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O(offset + length)

array_slice O(偏移量+长度)或O(n，如果长度= NULL

array_keys O (n)

array_values O (n)

array_reverse O (n)

array_pad O (pad_size)

array_flip O (n)

array_sum O (n)

array_product O (n)

array_reduce O (n)

array_filter O (n)

array_map O (n)

array_chunk O (n)

array_combine O (n)

我要感谢Eureqa使查找函数的大o变得很容易。这是一个惊人的免费的程序，可以为任意数据找到最佳拟合函数。

编辑:

对于那些怀疑PHP数组查找是O(N)的人，我已经编写了一个基准测试(对于大多数实际值，它们仍然有效地是O(1))。

php数组查找图

$tests = 1000000;
$max = 5000001;




for( $i = 1; $i <= $max; $i += 10000 ) {
//create lookup array
$array = array_fill( 0, $i, NULL );


//build test indexes
$test_indexes = array();
for( $j = 0; $j < $tests; $j++ ) {
$test_indexes[] = rand( 0, $i-1 );
}


//benchmark array lookups
$start = microtime( TRUE );
foreach( $test_indexes as $test_index ) {
$value = $array[ $test_index ];
unset( $value );
}
$stop = microtime( TRUE );
unset( $array, $test_indexes, $test_index );


printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
unset( $stop, $start );
}
小开

如果人们在实践中遇到键冲突的麻烦，他们会实现带有二级哈希查找或平衡树的容器。平衡树会给出O(log n)最坏情况和O(1)平均情况(哈希本身)。在大多数实际的内存应用程序中，这种开销并不值得，但也许有些数据库将这种形式的混合策略实现为默认情况。


提交答案