Lista de Big-O para funciones PHP

345

Después de usar PHP por un tiempo, noté que no todas las funciones integradas de PHP son tan rápidas como se esperaba. Considere estas dos posibles implementaciones de una función que encuentra si un número es primo usando una matriz de primos 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_arrayse implementa con una búsqueda lineal O (n) que disminuirá linealmente a medida que $prime_arraycrece. Donde la array_key_existsfunción se implementa con una búsqueda hash O (1) que no se ralentizará a menos que la tabla hash se llene extremadamente (en cuyo caso es solo O (n)).

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

¿Existe una lista de los grandes tiempos teóricos (o prácticos) de O para todas * las funciones PHP integradas?

* o al menos los interesantes

Por ejemplo, se me hace muy difícil predecir el gran O de las funciones enumeradas debido a la posible aplicación depende de las estructuras de datos básicos desconocida de PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine, str_replace(con las entradas de la matriz), etc.

Kendall Hopkins
fuente
31
Totalmente fuera de tema, pero 1 no es primo.
Jason Punyon
24
Las matrices en PHP son tablas hash. Eso debería decirle todo lo que necesita saber. La búsqueda de una clave en una tabla hash es O (1). La búsqueda de un valor es O (n), que no se puede superar en un conjunto sin clasificar. La mayoría de las funciones que le interesan son probablemente O (n). Por supuesto, si realmente quieres saber, puedes leer la fuente: cvs.php.net/viewvc.cgi/php-src/ext/standard/…
Frank Farmer
11
Para el registro, la implementación más rápida de lo que está tratando de hacer sería (en lugar de usar NULL para sus valores) usar truey luego probar la presencia usando isset($large_prime_array[$number]). Si no recuerdo mal, está en el orden de ser cientos de veces más rápido que la in_arrayfunción.
mattbasta
3
La notación Big O no se trata de velocidad. Se trata de limitar el comportamiento.
Gumbo
3
@Kendall no me estoy comparando array_key_exists, me estoy comparando in_array. in_arrayitera cada elemento de la matriz y compara el valor con la aguja que le pasa. Si cambia los valores a la clave (y simplemente reemplaza cada uno de los valores con un valor ficticio como true, usar issetes muchas veces más rápido. Esto se debe a que las claves de una matriz están indexadas por PHP (como una tabla hash). En consecuencia, la búsqueda una matriz de esta manera puede tener una mejora significativa en la velocidad.
mattbasta

Respuestas:

649

Como no parece que alguien haya hecho esto antes, pensé que sería una buena idea tenerlo como referencia en alguna parte. Sin embargo, he ido a través de puntos de referencia o de descremado de código para caracterizar las array_*funciones. He tratado de poner el Big-O más interesante cerca de la parte superior. Esta lista no esta completa.

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

Puntos interesantes :

  1. isset/ /array_key_exists es mucho más rápido que in_arrayyarray_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_pushes más rápido que array_shift/ array_unshiftdebido a la penalización de reindexación

Búsquedas :

array_key_existsO (n) pero muy cerca de O (1): esto se debe al sondeo lineal en colisiones, pero debido a que la posibilidad de colisiones es muy pequeña, el coeficiente también es muy pequeño. Me parece 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 un 50% de desaceleración.

isset( $array[$index] )O (n) pero muy cerca de O (1): utiliza la misma búsqueda que array_key_exists. Dado que es una construcción de lenguaje, almacenará en caché la búsqueda si la clave está codificada, lo que dará como resultado 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 a través de la matriz hasta que encuentra el valor.

array_search O (n): utiliza la misma función central 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): debe 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% intersecta O (ramparam_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 si la intersección 100% hace O (Max (param_i_size) * ∑param_i_count, para todo i), si la intersección 0% intersecta O (ramparam_i_size, para todo 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 se debe a que 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 volver a numerar

array_replace O (∑ array_i, para todo i)

Al azar :

shuffle En)

array_rand O (n): requiere una encuesta lineal.

Obvio Big-O :

array_fill En)

array_fill_keys En)

range En)

array_splice O (desplazamiento + longitud)

array_slice O (desplazamiento + longitud) u O (n) si longitud = NULL

array_keys En)

array_values En)

array_reverse En)

array_pad O (pad_size)

array_flip En)

array_sum En)

array_product En)

array_reduce En)

array_filter En)

array_map En)

array_chunk En)

array_combine En)

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

EDITAR:

Para aquellos que dudan de que las búsquedas de matriz PHP lo sean O(N), he escrito un punto de referencia para probar eso (todavía son efectivos O(1)para los valores más realistas).

gráfico de búsqueda de matriz 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 );
}
Kendall Hopkins
fuente
55
@Kendall: ¡Gracias! Leí un poco y resultó que PHP usa tablas hash 'anidadas' para colisiones. Es decir, en lugar de una estructura logn para colisiones, simplemente usa otra tabla hash. Y entiendo que prácticamente las tablas hash de PHP dan rendimiento O (1), o al menos O (1) en promedio, para eso están las tablas hash. Tenía curiosidad por saber por qué dijiste que son "realmente O (n)" y no "realmente O (logn)". Gran publicación por cierto!
Cam
10
¡Las complejidades de tiempo deben incluirse con la documentación! Elegir la función correcta puede ahorrarle mucho tiempo o decirle que evite hacer lo que planeaba: p ¡Gracias por esta lista ya!
Samuel
41
Sé que esto es viejo ... pero ¿qué? Esa curva no muestra O (n) en absoluto, muestra O (log n), en.wikipedia.org/wiki/Logarithm . Lo que también es exacto con lo que esperarías para los mapas hash anidados.
Andreas
55
¿Cuál es el Big-O de unset en un elemento de una matriz?
Chandrew
12
Si bien las tablas hash tienen una complejidad de búsqueda de O (n) en el peor de los casos, el caso promedio es O (1) y el caso particular que su punto de referencia está probando incluso está garantizado O (1), ya que es un índice numérico continuo, de base cero. matriz, que nunca tendrá colisiones hash. La razón por la que todavía está viendo una dependencia en el tamaño de la matriz no tiene nada que ver con la complejidad algorítmica, es causada por los efectos de caché de la CPU. Cuanto más grande es la matriz, más probable es que las búsquedas de acceso aleatorio provoquen errores de caché (y errores de caché más altos en la jerarquía).
NikiC
5

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

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

Dathan
fuente
Esto no es realmente una respuesta. Como dije en la pregunta, ya he intentado buscar en el código fuente de PHP. Dado que PHP está implementado, está escrito en C haciendo uso de macros complejas, lo que a veces puede dificultar "ver" la gran O subyacente para las funciones.
Kendall Hopkins
@Kendall Pasé por alto tu referencia a sumergirte en el código fuente. Sin embargo, hay una respuesta en mi respuesta: "No creo que haya una documentación exhaustiva específica de la complejidad algorítmica de los métodos PHP". "No" es una respuesta perfectamente válida. (c:
Dathan
4

Casi siempre quieres usar en issetlugar de array_key_exists. No estoy mirando las array_key_existspartes internas, pero estoy bastante seguro de que es O (N) porque itera sobre todas y cada una de las teclas de la matriz, mientras queisset intenta acceder al elemento usando el mismo algoritmo hash que se usa cuando se accede Un índice de matriz. Eso debería ser O (1).

Un "problema" 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 tecla y la última tecla.

ryeguy
fuente
99
Esto está mal. Estoy 100% seguro de que array_key_exists no tiene que iterar sobre cada clave. Si no cree, eche un vistazo al siguiente enlace. La razón por la que se establece es mucho más rápido es porque es una construcción de lenguaje. Lo que significa que no tiene la sobrecarga de hacer una llamada de función. Además, creo que podría estar almacenando en caché la búsqueda, debido a esto. Además, ¡esta no es una respuesta a LA PREGUNTA! Me gustaría una lista de Big (O) para las funciones de PHP (como dice la pregunta). Ni un solo punto de referencia de mis ejemplos. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/…
Kendall Hopkins
Si todavía no me cree, he creado un pequeño punto de referencia para demostrar el punto. pastebin.com/BdKpNvkE
Kendall Hopkins
Lo que está mal con su punto de referencia es que debe deshabilitar xdebug. =)
Guilherme Blanco
3
Hay dos razones fundamentales por las que desea utilizar isset sobre array_key_exists. Primero, isset es una construcción de lenguaje que mitiga el costo de una llamada de función. Esto es similar al argumento $arrray[] = $appendvs. array_push($array, $append)En segundo lugar, array_key_exists también diferencia entre valores no establecidos y valores nulos. For $a = array('fred' => null); array_key_exists('fred', $a)devolverá verdadero mientras isset($['fred'])que devolverá falso. Este paso adicional no es trivial y aumentará considerablemente el tiempo de ejecución.
orca
0

Si la gente tuviera problemas en la práctica con colisiones clave, implementaría contenedores con una búsqueda secundaria de hash o un árbol equilibrado. El árbol equilibrado daría O (log n) el peor comportamiento 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 tal vez hay bases de datos que implementan esta forma de estrategia mixta como su caso predeterminado.

Josh Stern
fuente