O的PHP函数
现在使用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（1）不会变慢。
到目前为止，我不得不通过反复试验来发现big-O，偶尔还要看源代码。 现在对于这个问题...
是否有一个理论（或实际）的大O时代的列表？内置函数的PHP？
*或至少有趣的
例如发现它很难预测什么样的功能，大O上市，因为可能的实现依赖于PHP的核心未知数据结构：array_merge，array_merge_recursive，array_reverse，array_intersect，array_combine，str_replace函数（与数组输入）等。
由于它似乎并没有任何人做过，所以我认为将它作为参考的地方是个好主意。 我已经去了，无论是通过基准或代码撇取来表征array_*函数。 我试图把更有趣的Big-O放在最前面。 该列表不完整。
注意：尽管它实际上是O（n），但假定进行哈希查找计算的所有Big-O都是O（1）。 n的系数非常低，在查找Big-O的特性开始生效之前，存储足够大的阵列的内存开销会损害您。 例如，在N = 1和N = 1,000,000时对array_key_exists的调用之间的差别是时间增加约50％。
有趣的点 ：
isset / array_key_exists比in_array和array_search + （联合）比array_merge快一点（看起来更好）。 但它的工作方式不同，所以请记住。 shuffle与array_rand在同一个Big-O层上 array_pop / array_push比array_shift / array_unshift快 查找 ：
array_key_exists O（n）但非常接近O（1） - 这是因为碰撞中的线性轮询，但由于碰撞的几率非常小，系数也非常小。 我发现你把HASH查找当作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，对于所有我） - 它必须重新索引所有的键
阵列相交，联合，减法 ：
array_intersect_key如果相交100％做O（Max（param_i_size）*Σparam_i_count，对于所有我），如果相交0％相交O（Σparam_i_size，对于所有我）
array_intersect如果相交100％做O（n ^ 2 *Σparam_i_count，对于所有我），如果相交0％相交O（n ^ 2）
array_intersect_assoc如果相交100％做O（Max（param_i_size）*Σparam_i_count，对于所有我），如果相交0％相交O（Σparam_i_size，对于所有我）
array_diff O（πparam_i_size，对于所有我） - 这是所有param_sizes的产物
array_diff_key O（Σparam_i_size，对于i！= 1） - 这是因为我们不需要遍历第一个数组。
array_merge O（Σarray_i，i！= 1） - 不需要迭代第一个数组
+ （union）O（n），其中n是第二个数组的大小（即array_first + array_second） - 比array_merge少开销，因为它不必重新编号
array_replace O（Σarray_i，对于所有我）
随机 ：
shuffle O（n）
array_rand O（n） - 需要线性轮询。
明显的大O ：
array_fill O（n）
array_fill_keys O（n）
range O（n）
array_splice O（offset + length）
array_slice O（offset + length）或O（n）如果length = 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) ）。
$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.15fn", $i, $stop - $start ); //time per 1mil lookups
unset( $stop, $start );
}
你几乎总是想使用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秒
当然，这并不显示时间复杂性，但它确实显示了2个函数如何相互比较。
要测试时间复杂性，请比较在第一个键和最后一个键上运行这些功能所需的时间。
你特别描述的情况的解释是，关联数组被实现为散列表 - 所以按键（和相应的array_key_exists ）查找是O（1）。 但是，数组并没有按值进行索引，所以在一般情况下，发现数组中是否存在值的唯一方法是线性搜索。 那里并不奇怪。
我不认为有关PHP方法的算法复杂性的具体综合文档。 但是，如果需要付出很大努力，您可以随时查看源代码。
链接地址: http://www.djcxy.com/p/6699.html上一篇: O for PHP functions