¿Por qué Lua está diseñado de tal manera que obtener el tamaño de una tabla es O (n) en el tamaño de la tabla?

Pregunta realmente fascinante. Pensé que sabía la respuesta, pero mis suposiciones resultaron estar equivocadas. La respuesta corta es que el cálculo de la longitud primitiva (ignorando cualquier método __len definido por el __len ) en realidad toma tiempo [matemático] O (\ log n) [/ matemático] en la longitud de la tabla, y el operador de longitud primitiva se especifica forma en que esta complejidad me parece óptima. Si bien puedo pensar en una forma igualmente razonable de definir el operador que permita una implementación de tiempo constante, vale la pena entender por qué la especificación actual conduce a un algoritmo logarítmico.

El operador de longitud primitiva # calcula la longitud de una tabla de acuerdo con la siguiente regla:

La longitud de una tabla t se define como cualquier índice entero n tal que t[n] no es nil y t[n+1] es nil ; además, si t[1] es nil , n puede ser cero. Para una matriz regular, con valores no nil de 1 a un n dado, su longitud es exactamente ese n , el índice de su último valor. Si la matriz tiene “agujeros” (es decir, valores nil entre otros valores no nil ), entonces #t puede ser cualquiera de los índices que preceden directamente a un valor nil (es decir, puede considerar cualquier valor nil como el final de la matriz).

• ¿Por qué el NN recurrente agrega el paso T-1 a la entrada actual pero se concatena?
• ¿Cuál es la diferencia entre los algoritmos Reheap up y Reheap down?
• ¿Cuál es el algoritmo más eficiente para encontrar el késimo elemento más pequeño en una matriz que tiene n elementos desordenados?
• ¿Cuál crees que es el algoritmo de aprendizaje automático más inteligente?
• ¿Cómo pueden los estudiantes de electricidad y electrónica llegar a ser buenos en algoritmos y estructuras de datos?

Por supuesto, siempre que haya una ambigüedad en una definición, el tiempo de ejecución debería preferir la alternativa más barata de calcular. Confío en que el enfoque [matemático] O (n) [/ matemático] es obvio, pero lo desafiaría, antes de revelar la verdadera implementación, a pensar en un enfoque que tome tiempo logarítmico.

Aquí está la parte relevante del código fuente de Lua:

 static int unbound_search (Table *t, unsigned int j) { unsigned int i = j; /* i is zero or a present index */ j++; /* find `i' and `j' such that i is present and j is not */ while (!ttisnil(luaH_getint(t, j))) { i = j; j *= 2; if (j > cast(unsigned int, MAX_INT)) { /* overflow? */ /* table was built with bad purposes: resort to linear search */ i = 1; while (!ttisnil(luaH_getint(t, i))) i++; return i - 1; } } /* now do a binary search between them */ while (j - i > 1) { unsigned int m = (i+j)/2; if (ttisnil(luaH_getint(t, m))) j = m; else i = m; } return i; } 

Enlace: http://www.lua.org/source/5.2/lt…

En el peor de los casos (una matriz densa), lleva tiempo [matemático] O (\ log n) [/ matemático] asegurarse de que i marque un índice ocupado (no nil ) y j marque un índice desocupado ( nil ), ignorando El improbable caso de un desbordamiento de enteros.

Una vez que i marca un índice ocupado j marca un índice desocupado, el bucle while final realiza una búsqueda binaria en la región limitada por j . Esta región podría ser tan grande como la tabla misma (p. Ej., Si i es el índice del último elemento de la tabla y j == 2 * i ), por lo que esta búsqueda binaria también toma [matemáticas] O (\ log n) [ / matemáticas] tiempo.

Dos operaciones [math] O (\ log n) [/ math] -time suman una operación [math] O (\ log n) [/ math], porque la notación asintótica ignora factores constantes. Entonces ahí lo tienes.

Ahora, ¿podemos hacerlo mejor? Recuerde que el operador # primitivo puede devolver técnicamente el índice de cualquier elemento seguido de nil .

Para evaluar el tamaño de una tabla en tiempo constante, lo que supongo es su expectativa, la longitud actual de la tabla debe almacenarse en algún lugar de la memoria y debe mantenerse actualizada a medida que la tabla cambia. Si la contabilidad correcta empeora el rendimiento de las operaciones de la tabla de manera notable, entonces se convierte en una mala idea y usted tiene su respuesta.

¿Qué sucede si el tiempo de ejecución de Lua simplemente realiza un seguimiento del índice numérico máximo actualmente ocupado? Este índice siempre debe contar como una longitud válida (recuerde que las tablas Lua se indexan a partir de 1 en lugar de 0), y cada vez que agregue un nuevo índice numérico a la tabla, sería trivial decidir si el máximo actual debería aumentar o no. permanece igual El operador de longitud primitiva podría devolver este valor máximo sin realizar ningún cálculo adicional.

Pero, ¿qué sucede si elimina el elemento en el índice numérico máximo actual? Luego tiene que encontrar el segundo índice numérico más grande y convertirlo en el nuevo máximo, y la estructura de datos más eficiente que conozco para encontrar el segundo índice más grande es un montón dinámico máximo . ¡Pero Ay! La inserción y eliminación de un máximo dinámico binario son operaciones [math] O (\ log n) [/ math], que es una sobrecarga de contabilidad inaceptable cuando se inserta un elemento en una tabla, porque uno esperaría que la inserción tome tiempo constante

No pretendo haber demostrado que el algoritmo [math] O (\ log n) [/ math] es óptimo, pero no veo ninguna forma obvia de mejorarlo, mientras mantengo la semántica del operador # . Tenga en cuenta que realizar un seguimiento del número de índices numéricos actualmente ocupados en la tabla sería trivial si ignoramos los agujeros, y ese comportamiento probablemente sería mucho menos sorprendente para los nuevos usuarios de Lua. Quizás otros puedan proporcionar una idea de por qué esa no es la forma en que Lua define el operador de longitud primitiva.