PHP的Big-O列表-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

PHP的Big-O列表

保持可爱mmm 2020-01-15 16:54:12 90

在使用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)随$prime_array增长线性降低。该array_key_exists函数是用哈希查找O(1)来实现的,除非哈希表被填充得足够多(在这种情况下,它仅为O(n)),否则它不会减慢速度。

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

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

*或至少是有趣的

举例来说,我觉得很难预测的上市功能的大O,因为可能的实现依赖于PHP的核心未知数据结构:array_merge,array_merge_recursive,array_reverse,array_intersect,array_combine,str_replace(与阵列输入)等。

缓存 PHP
分享到
取消 提交回答
全部回答(1)
  • 保持可爱mmm
    2020-01-15 16:54:32

    由于似乎没有人做过此事,因此我认为最好在某个地方提供参考。我已经通过基准测试或代码掠过来表征这些array_*功能。我试图将更有趣的Big-O放在顶部。此列表不完整。

    注意:假设是哈希查找,所有计算出来的Big-O都是O(1),即使它实际上是O(n)。n的系数是如此之低,在大Big-O的特征开始生效之前,存储足够大的数组的内存开销会伤害您。例如,array_key_exists在N = 1和N = 1,000,000时的通话时间差为〜50%。

    有趣的地方:

    isset/ array_key_exists比in_array和快得多array_search +(联盟)比array_merge(看起来更好)快一点。但是它的工作方式有所不同,因此请记住这一点。 shuffle 在与Big-O相同的层上 array_rand 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,对于所有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%对所有i执行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,for all i)-那是所有param_sizes的乘积

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

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

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

    array_replace O(∑ array_i,对于所有i)

    随机:

    shuffle 上)

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

    明显的Big-O:

    array_fill 上)

    array_fill_keys 上)

    range 上)

    array_splice O(偏移量+长度)

    array_slice O(偏移量+长度)或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)对于大多数实际值它们仍然有效)。

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

    }

    问题来源于stack overflow

    0 0
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题