PHP函数的Big-O列表

Question

在使用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)实现的,线性搜索O(n)随着in_array增长线性减慢.其中$prime_array函数是使用散列查找O(1)实现的,除非哈希表得到极大填充(在这种情况下它只是O(n)),否则它不会减慢速度.

到目前为止,我必须通过反复试验来发现big-O,并偶尔查看源代码.现在问题......

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

*或至少是有趣的

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

Answer 1

因为在我认为将它作为某个地方的参考之前,似乎没有人这样做过.我已经走了,无论是通过基准测试还是代码略读来表征array_*功能.我试图将更有趣的Big-O放在顶部附近.此列表不完整.

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

有趣的点:

1. isset/ array_key_exists比in_array和快得多array_search
2. +(联盟)比array_merge(并且看起来更好)快一点.但它的确有不同的作用,所以请记住这一点.
3. shuffle 与...相同的Big-O等级 array_rand
4. array_pop/ array_push快于array_shift/ array_unshift由于重新索引处罚

查找:

array_key_existsO(n)但非常接近O(1) - 这是因为碰撞中的线性轮询,但由于碰撞的机会非常小,因此系数也非常小.我发现你将哈希查找视为O(1)以提供更逼真的big-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,对于所有我)

array_pop O(1)

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

array_unshift O(n +Σvar_i,对于所有i) - 它必须重新索引所有键

数组交集,联合,减法:

array_intersect_key 如果交点100%做O(Max(param_i_size)*Σparam_i_count,对于所有i),如果交点0%与O相交(Σparam_i_size,对于所有i)

array_intersect 如果交点100%做O(n ^ 2*Σparam_i_count,对于所有i),如果交点0%与O(n ^ 2)相交

array_intersect_assoc 如果交点100%做O(Max(param_i_size)*Σparam_i_count,对于所有i),如果交点0%与O相交(Σparam_i_size,对于所有i)

array_diff O(πparam_i_size,对于所有我) - 这是所有param_sizes的产物

array_diff_key O(Σparam_i_size,对于i!= 1) - 这是因为我们不需要迭代第一个数组.

array_merge O(Σray_i,i!= 1) - 不需要迭代第一个数组

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

array_replace O(Σarray_i,对于所有我)

随机:

shuffle 上)

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

明显的大O:

array_fill 上)

array_fill_keys 上)

range 上)

array_splice O(偏移+长度)

array_slice 如果length = NULL,则为O(偏移+长度)或O(n)

array_keys 上)

array_values 上)

array_reverse 上)

array_pad O(pad_size)

array_flip 上)

array_sum 上)

array_product 上)

array_reduce 上)

array_filter 上)

array_map 上)

array_chunk 上)

array_combine 上)

我要感谢Eureqa让我们很容易找到函数的Big-O.这是一个惊人的免费程序,可以找到任意数据的最佳拟合函数.

编辑:

对于那些怀疑PHP数组查找的人O(N),我已经编写了一个基准来测试它(它们仍然可以有效地O(1)用于最实际的值).

$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 );
}

Answer 2

您几乎总是想使用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 秒

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

要测试时间复杂度，请比较在第一个键和最后一个键上运行这些函数之一所需的时间。

Answer 3

您具体描述的情况的解释是，关联数组被实现为哈希表-因此按键查找（相应地，array_key_exists）为O（1）。但是，数组不是按值索引的，因此在一般情况下发现数组中是否存在值的唯一方法是线性搜索。那里并不奇怪。

我认为没有关于PHP方法算法复杂性的具体综合文档。但是，如果您有足够大的忧虑需要付出努力，则可以随时查看源代码。