una - ¿Cómo se implementa la matriz de PHP en el nivel C?
matrices en php (5)
Como las matrices PHP son mapas ordenados (incluso cuando se utilizan índices enteros contiguos) array_rand() probablemente tenga que elaborar una lista de claves para seleccionar un elemento. Supongo que sería prohibitivo el espacio y el tiempo ineficaces para almacenar en caché la lista de claves (frecuentemente invalidadas), de modo que cada llamada incurrirá al menos en un cruce de O (n) y un costo de construcción.
Debido a que su implementación de rand(... length ...) aprovecha el conocimiento especial que tiene de que las claves son enteros contiguos, obtendrá costos de búsqueda O (log n). Esto parece consistente con los datos de Chacha102.
La array PHP es una de las características principales de PHP. Es escaso, permite claves de varios tipos en la misma matriz y admite conjunto, diccionario, matriz, pila / cola y funcionalidad iterativa.
Pero después de trabajar con PHP por un tiempo, descubrí que bastantes de las funciones de array_* son mucho más lentas de lo que pensarías a primera vista. Como en el caso de array_rand en una matriz muy grande (10000+). array_rand es tan lento, de hecho, que en los casos en los que utiliza la matriz php como matriz indexada, una función como rand( 0, array_length( $array ) - 1 ) ejecuta MUCHO más rápido que array_rand .
Ahora en mi pregunta.
¿Cómo se implementa la matriz de PHP en el nivel C? Esto sería muy útil para predecir el Big O de una función que utiliza en gran medida las diferentes funcionalidades del tipo de datos del array PHP.
Después de leer zend / zend_hash.hy ext / standard / array.c, creo que encontré la respuesta (gracias a Chris y gumbo por las sugerencias).
La matriz PHP es una tabla hash encadenada (búsqueda de O (c) y O (n) en las colisiones de teclas) que permite claves int y de cadena. Utiliza 2 algoritmos hash diferentes para ajustar los dos tipos en el mismo espacio de clave hash. Además, cada valor almacenado en el hash está vinculado al valor almacenado antes y al valor almacenado después (lista enlazada). También tiene un puntero temporal que se utiliza para contener el elemento actual para que el hash pueda repetirse.
El truco para la función array_rand es que para asegurar que la clave sea verdaderamente aleatoria, la función array_rand debe iterar sobre la matriz rand(0, count($array)) veces (O (n)). Esto se debe a que no hay forma de moverse a un desplazamiento en la tabla hash en el tiempo O (c) porque no hay garantía de que no falten claves en el rango.
Este descubrimiento me ha preocupado un poco, porque significa que NO hay ningún tipo de datos en PHP que tenga características de matriz C normales. Ahora la mayoría de las veces esto está bien, porque las búsquedas de hash son mucho más rápidas, pero las fallas se muestran en casos como array_rand .
Otra cosa que también me preocupaba era la diferencia entre la implementación de array_key_exists y in_array . array_key_exists usa la búsqueda de hash (la mayoría de las veces O (c)) para ver si una clave está en la matriz, mientras que in_array tiene que buscar linealmente el hash (O (n)).
Considere los dos ejemplos a continuación:
Versión de in_array
$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
//we found a value
}
Versión array_key_exists
$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
//we found a value, err key
}
Mientras que la versión de in_array parece mucho más limpia y simple de entender, en realidad es muy lenta en arreglos grandes (O (n)), donde array_key_exists (a pesar de ser un nombre molesto) es muy rápida (O (c) o cercana).
En conclusión: desearía que hubiera una bandera transparente en la estructura de datos de Zend HashTable que se establecería en los casos en que la matriz se creó usando array_push o array[] = $value que permitiría escalar como una matriz C en lugar de un enlace lista.
Eche un vistazo a zend/zend_hash.c y zend/zend_hash.h
No sé c, pero para mí, parece una tabla de hash encadenada.
Las matrices asociativas de PHP son, de hecho, la implementación de HashTables .
Internamente, es posible hacer matrices numéricas o matrices asociativas. Si los combinas, es una matriz asociativa.
En matrices numéricas, es muy similar a C. Tiene una matriz de punteros a las estructuras de ZVAL.
Debido a que los punteros tienen longitud fija (llamémoslo n), el cálculo del desplazamiento (x) es fácil: x * n.
En PHP, los tipos son estructuras ZVAL (porque de esa manera implementa tipos dinámicos), pero también ayuda en la matriz asociativa, porque puede asumir una longitud fija. Por lo tanto, incluso si el acceso directo a la matriz es más lento, todavía se considera O (1).
Entonces, ¿qué sucede en las llaves de cadena? PHP usa la función hash para convertirlos a intergers.
La búsqueda en matriz numérica y asociativa tiene una eficiencia similar, porque internamente son todos numéricos.
Solo el acceso directo a las teclas de matriz es más lento, debido al nivel adicional (función de almohadilla).
Vea este comentario en la documentación que confirma su dilema de que array_rand, mientras que es rápido para matrices pequeñas, escala muy pobremente.
Modifiqué fake_array_rand para siempre devolver solo 1 elemento, e hice algunos benchmarks contra llamar array_rand con el segundo parámetro como 1. Ejecuté 100 muestras para cada función para cada número de elementos y obtuve el resultado promedio. Mientras que la matriz interna_y es más rápida para una pequeña cantidad de elementos, se escala muy pobremente.
1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand 10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand 100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand 1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand 10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand 100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand 1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand <?php function fake_array_rand ($array) { $count = count ($array); # Help keep the number generator random :) $randval and usleep ("0.$randval"); # Seed the random number generator # Generate a random number srand ((double) microtime() * 10000000); $randval = rand(); # Use the random value to ''pick'' an entry from the array # Count the number of times that the entry is picked ++$index[$randval % $count]; return $array[$randval % $count]; } ?>