predefinidas - Lista de Big-O para funciones PHP

introduccion a php pdf

Question

Después de usar PHP por un tiempo, he notado que no todo PHP incorporado funciona tan rápido como se esperaba. Considere las siguientes dos posibles implementaciones de una función que encuentra si un número es primo usando una matriz de primos almacenada en caché.

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

Esto se debe a que in_array se implementa con una búsqueda lineal O (n) que se ralentizará linealmente a medida que $prime_array . Donde la función array_key_exists se implementa con una búsqueda de hash O (1) que no se ralentizará a menos que la tabla de hash se llene extremadamente (en cuyo caso solo es O (n)).

Hasta ahora he tenido que descubrir las grandes O mediante prueba y error, y ocasionalmente mirando el código fuente . Ahora para la pregunta ...

¿Hubo una lista de los grandes tiempos teóricos (o prácticos) de todas las funciones incorporadas en PHP?

* o al menos los interesantes.

Por ejemplo, es muy difícil predecir cuál es la O grande de funciones enumeradas porque la posible implementación depende de estructuras de datos centrales desconocidas de PHP: array_merge, array_merge_recursive, array_reersect, array_intersect, array_combine, str_replace (con entradas de array), etc.

Answer 1

Casi siempre desea usar isset lugar de array_key_exists . No estoy mirando las array_key_exists internas, pero estoy bastante seguro de que array_key_exists es O (N) porque se repite en todas y cada una de las claves de la matriz, mientras que isset intenta acceder al elemento utilizando el mismo algoritmo hash que se usa cuando se accede a un índice de matriz. Eso debería ser O (1).

Un "gotcha" a tener en cuenta es este:

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

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

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

Tenía curiosidad, así que comparé la diferencia:

<?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 segundos
array_key_exists: 2.33202195168 segundos

Por supuesto, esto no muestra la complejidad del tiempo, pero sí muestra cómo las 2 funciones se comparan entre sí.

Para probar la complejidad del tiempo, compare la cantidad de tiempo que lleva ejecutar una de estas funciones en la primera y en la última.

Answer 2

Dado que no parece que alguien haya hecho esto antes, pensé que sería una buena idea tenerlo como referencia en algún lugar. Sin embargo, he ido y ya sea a través de benchmark o de codificación de código para caracterizar las funciones array_* . He intentado poner el Big-O más interesante cerca de la cima. Esta lista no esta completa.

Nota: Todo el Big-O en el que se calculó asumiendo que una búsqueda de hash es O (1) aunque sea realmente O (n). El coeficiente de la n es tan bajo, la sobrecarga del ariete de almacenar una matriz lo suficientemente grande le haría daño antes de que las características de búsqueda Big-O comenzaran a tener efecto. Por ejemplo, la diferencia entre una llamada a array_key_exists en N = 1 y N = 1,000,000 es un aumento de tiempo de ~ 50%.

Puntos de interés :

1. isset / array_key_exists es mucho más rápido que in_array y array_search
2. + (union) es un poco más rápido que array_merge (y se ve mejor). Pero funciona de manera diferente, así que tenlo en cuenta.
3. shuffle está en el mismo nivel Big-O que array_rand
4. array_pop / array_push es más rápido que array_shift / array_unshift debido a la penalización de re-indexación

Búsquedas :

array_key_exists O (n) pero muy cerca de O (1): esto se debe a un sondeo lineal en colisiones, pero debido a que la probabilidad de colisiones es muy pequeña, el coeficiente también es muy pequeño. Encuentro que tratas las búsquedas de hash como O (1) para dar un big-O más realista. Por ejemplo, la diferencia entre N = 1000 y N = 100000 es solo una ralentización del 50%.

isset( $array[$index] ) O (n) pero muy cerca de O (1): utiliza la misma búsqueda que array_key_exists. Dado que se trata de una construcción de lenguaje, almacenará en caché la búsqueda si la clave está codificada, lo que resultará en una aceleración en los casos en que la misma clave se use repetidamente.

in_array O (n): esto se debe a que realiza una búsqueda lineal en la matriz hasta que encuentra el valor.

array_search O (n): utiliza la misma función básica que in_array pero devuelve valor.

Funciones de cola :

array_push O (∑ var_i, para todo i)

array_pop O (1)

array_shift O (n) - tiene que reindexar todas las claves

array_unshift O (n + ∑ var_i, para todo i) - tiene que reindexar todas las claves

Intersección de matriz, unión, resta :

array_intersect_key si la intersección 100% hace O (Max (param_i_size) * ∑param_i_count, para todo i), si la intersección 0% interseca O (∑param_i_size, para todo i)

array_intersect si la intersección 100% hace O (n ^ 2 * ∑param_i_count, para todo i), si la intersección 0% intersecta O (n ^ 2)

array_intersect_assoc if intersection 100% do O (Max (param_i_size) * ∑param_i_count, para todo i), si intersección 0% intersecta O (∑param_i_size, for all i)

array_diff O (π param_i_size, para todo i) - Eso es producto de todos los param_sizes

array_diff_key O (∑ param_i_size, para i! = 1) - esto es porque no necesitamos iterar sobre la primera matriz.

array_merge O (∑ array_i, i! = 1) - no necesita iterar sobre la primera matriz

+ (unión) O (n), donde n es el tamaño de la segunda matriz (es decir, array_first + array_second) - menos sobrecarga que array_merge ya que no tiene que renumerar

array_replace O (∑ array_i, para todos los i)

Aleatorio

shuffle O (n)

array_rand O (n) - Requiere una encuesta lineal.

Obvio Big-O :

array_fill O (n)

array_fill_keys O (n)

range O (n)

array_splice O (offset + longitud)

array_slice O (desplazamiento + longitud) o O (n) si longitud = 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)

Me gustaría agradecer a Eureqa por facilitar la búsqueda del Big-O de las funciones. Es un increíble programa gratuito que puede encontrar la mejor función de ajuste para datos arbitrarios.

EDITAR:

Para aquellos que dudan de que las búsquedas de matrices de PHP sean O(N) , he escrito un punto de referencia para probar que (aún son efectivamente O(1) para los valores más realistas).

$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 3

La explicación para el caso que describe específicamente es que las matrices asociativas se implementan como tablas hash, por lo que la búsqueda por clave (y, en array_key_exists , array_key_exists ) es O (1). Sin embargo, las matrices no se indexan por valor, por lo que la única forma en el caso general de descubrir si existe un valor en la matriz es mediante una búsqueda lineal. No hay sorpresa allí.

No creo que haya una documentación exhaustiva específica de la complejidad algorítmica de los métodos de PHP. Sin embargo, si es una preocupación lo suficientemente grande como para justificar el esfuerzo, siempre puede consultar el código fuente .

Answer 4

Si la gente tuviera problemas en la práctica con colisiones clave, implementarían contenedores con una búsqueda de hash secundaria o un árbol equilibrado. El árbol equilibrado daría O (log n) peor comportamiento de caso y O (1) promedio. caso (el hash mismo). La sobrecarga no vale la pena en la mayoría de las aplicaciones prácticas de memoria, pero quizás hay bases de datos que implementan esta forma de estrategia mixta como su caso predeterminado.