php - 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) 实现，它将线性减慢为 $prime_array成长。凡array_key_exists函数是通过哈希查找 O(1) 实现的，除非哈希表变得非常填充(在这种情况下它只是 O(n))，否则不会减慢速度。

到目前为止，我不得不通过反复试验发现大 O，偶尔 looking at the source code .现在的问题...

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

*或至少是有趣的

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

Answer 1

因为在我认为最好将它放在某处以供引用之前似乎没有人这样做过。我已经通过基准测试或代码略读来表征 array_*功能。我试图将更有趣的 Big-O 放在靠近顶部的位置。这份 list 并不完整。

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

有趣的点 :

isset/array_key_exists比in_array快得多和 array_search

+ (union) 比 array_merge 快一点(而且看起来更好)。但它的工作方式有所不同，所以请记住这一点。

shuffle与 array_rand 处于同一 Big-O 层

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, 对于所有 i)
array_pop O(1)
array_shift O(n) - 它必须重新索引所有的键
array_unshift O(n + ∑ var_i, for all i) - 它必须重新索引所有的键

数组交、并、减 :
array_intersect_key如果相交 100% 做 O(Max(param_i_size)*∑param_i_count, for all i), 如果相交 0% 相交 O(∑param_i_size, for all i)
array_intersect如果相交 100% 做 O(n^2*∑param_i_count, for all i)，如果相交 0% 相交 O(n^2)
array_intersect_assoc如果相交 100% 做 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_sizes 的乘积
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, 对于所有 i )

随机 :
shuffle在)
array_rand O(n) - 需要线性轮询。

明显的大O :
array_fill在)
array_fill_keys在)
range在)
array_splice O(偏移量 + 长度)
array_slice O(offset + length) 或 O(n) 如果长度 = NULL
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 );
}