El operador de longitud: una frontera, no un contador

De todas las trampas que Lua le tiende a quien llega de otro lenguaje, ninguna se cobra tantas víctimas como el operador de longitud. La expresión #t parece un contador y no lo es, parece constante y no lo es, y parece determinista para un conjunto dado de claves y tampoco lo es. El manual de referencia es escrupulosamente honesto al respecto: define el operador solo para secuencias y, fuera de ellas, promete únicamente devolver una frontera cualquiera. La mayoría de los programadores lee esa frase como una advertencia legalista y sigue adelante. Después de esta lección la vas a leer como lo que es: la descripción exacta de un algoritmo que puedes reconstruir, predecir y, cuando haga falta, evitar por completo.

Secuencias, fronteras y lo que promete el manual

Una tabla es una secuencia cuando el conjunto de sus claves enteras positivas es exactamente 1, 2, ..., n para algún n no negativo, sin faltar ninguna. Sobre una secuencia, #t devuelve n, sin ambigüedad, y todas las funciones de la biblioteca table funcionan como esperas.

Una frontera de una tabla es cualquier entero no negativo n que cumpla una de estas dos condiciones: o bien t[n] no es nil y t[n+1] sí lo es, o bien n vale cero y t[1] es nil. En una secuencia hay exactamente una frontera y coincide con la longitud. En una tabla con agujeros hay varias, y el manual dice que #t devuelve una de ellas, sin comprometerse a cuál.

local t = {}
t[1] = "a"
t[2] = "b"
t[4] = "d"           -- agujero en la posicion 3

-- Fronteras validas: 2 (porque t[3] es nil) y 4 (porque t[5] es nil).
-- El operador puede devolver cualquiera de las dos, y la eleccion
-- depende de como se construyo la tabla, no de las claves que contiene.
print(#t)

Conviene subrayar lo que la definición de frontera no dice. No dice nada sobre el número de elementos: una tabla con las claves 1, 2 y 1000 tiene la frontera 2 y también la 1000, y ninguna de las dos es tres. No dice nada sobre claves no enteras: las claves de texto de una tabla son invisibles para el operador, de modo que una tabla con veinte campos y ningún índice numérico tiene longitud cero. Y no dice nada sobre estabilidad: la frontera devuelta puede cambiar entre dos llamadas idénticas si entre medias la tabla se redimensionó, aunque su contenido observable sea el mismo.

Esto no es indefinición gratuita. Es la contrapartida directa de la representación dual: como el operador está autorizado a devolver cualquier frontera, la implementación puede buscar la que le salga barata con la estructura interna que tenga en ese momento, en lugar de recorrer la tabla entera. La ambigüedad de la especificación es lo que compra el rendimiento.

Lo que hace de verdad

El algoritmo real tiene tres caminos, ordenados de más barato a más caro, y elige el primero que sea aplicable.

flowchart TD
A[Consulta de longitud] --> B[El hueco del limite del vector esta vacio]
B -->|si| C[Busqueda binaria dentro del vector]
C --> Z[Devolver la frontera y cachear el limite]
B -->|no| D[El vector esta lleno hasta el final]
D --> E[La parte hash esta vacia]
E -->|si| F[Devolver el tamano del vector]
E -->|no| G[Duplicar j hasta que t de j sea nil]
G --> H[Busqueda binaria entre i y j sobre la parte hash]
H --> Z

Camino uno. Si el último hueco del vector está vacío, la frontera está dentro del vector y se localiza con una búsqueda binaria clásica sobre las posiciones 1 a N. Esto explora del orden de log2(N) posiciones: para un vector de un millón de huecos, unas veinte lecturas.

Camino dos. Si el vector está lleno hasta su última posición y la parte hash está vacía, la frontera es exactamente el tamaño del vector y se devuelve sin buscar nada. Este es el caso de la inmensa mayoría de las secuencias reales, y por eso #t se comporta en la práctica como una operación constante.

Camino tres. Si el vector está lleno y la dispersión no está vacía, la secuencia continúa dentro de la dispersión. Aquí se hace primero una búsqueda no acotada: se parte de un índice i conocido como no nulo y se duplica un índice j hasta encontrar un t[j] nulo, y después una búsqueda binaria entre ambos. El coste sigue siendo logarítmico, pero cada paso es una consulta con hash en lugar de una lectura indexada, así que la constante es sensiblemente peor.

-- Version en Lua del camino tres, para fijar la idea.
local function frontera_en_hash(t, i)   -- t[i] no es nil
  local j = i + 1
  while t[j] ~= nil do
    i = j
    if j > 2^30 then                    -- proteccion contra tablas monstruosas
      i = 1; while t[i] ~= nil do i = i + 1 end
      return i - 1
    end
    j = j * 2
  end
  while j - i > 1 do                    -- busqueda binaria: t[i] vive, t[j] no
    local m = (i + j) // 2
    if t[m] ~= nil then i = m else j = m end
  end
  return i
end

-- Los tres caminos, provocados a proposito.
local a = table.create(1024)
for i = 1, 1024 do a[i] = i end
a[900] = nil          -- vector lleno hasta el final: camino dos, devuelve 1024
a[1024] = nil         -- ultimo hueco vacio: camino uno, busqueda binaria

local b = {}
for i = 1, 8 do b[i] = i end
for i = 9, 20 do b[i] = i end   -- parte de la secuencia acaba en la dispersion
print(#b)             -- camino tres: duplicacion mas busqueda binaria

Un último matiz de implementación que explica la sensación de que #t es gratis: el campo que delimita el vector se usa además como caché de la última frontera encontrada. Cuando una búsqueda binaria localiza una frontera dentro del vector, la implementación puede guardarla ahí, de modo que la siguiente consulta sobre una tabla que no ha cambiado responda de inmediato. Es la razón de que medir #t dentro de un bucle rara vez aparezca en un perfilado, y también de que dos tablas con las mismas claves respondan cosas distintas: una de ellas lleva encima una caché con una frontera que la otra nunca calculó.

Las sorpresas, explicadas

print(#{1, 2, nil, 4})        --> 4   el constructor preasigna un vector de 4
                              --      y la ultima posicion no esta vacia

local t = {}
t[1], t[2], t[4] = 1, 2, 4
print(#t)                     --> 2   construida asi, la 4 vive en la dispersion

local u = {1, 2, 3, 4}
u[4] = nil
print(#u)                     --> 3   el vector sigue siendo de 4, con el
                              --      ultimo hueco vacio: busqueda binaria

local v = {1, 2, 3, 4}
v[3] = nil
print(#v)                     --> 4   el ultimo hueco esta lleno: camino dos

Los cuatro casos usan claves parecidas y dan resultados distintos, y ninguno es un fallo. El constructor {1, 2, nil, 4} es especial porque el compilador conoce el número de elementos y preasigna un vector de cuatro; el nil intermedio ocupa su hueco. La construcción por asignaciones sueltas no tiene esa información y deja la clave 4 en la dispersión, donde el camino uno la encuentra parando en 2. Y los dos últimos ejemplos muestran lo esencial: con el mismo vector de tamaño cuatro, borrar el último elemento cambia de camino y borrar el tercero no.

El contagio es lo que hace que esto importe de verdad. #t no es un operador aislado que puedas evitar: es la definición de longitud que usa media biblioteca estándar, y cada una de esas funciones hereda su ambigüedad sin avisar.

Fíjate en que ipairs no aparece en esa lista, y no es casualidad: desde Lua 5.3 no consulta la frontera en absoluto. Recorre desde 1 incrementando hasta encontrar el primer nil, lo que le da un comportamiento perfectamente definido —aunque no siempre el que quieres— sobre cualquier tabla, con o sin agujeros. Cuando dudes de la integridad de una secuencia, ipairs es el iterador honesto y #t el que se calla lo que no sabe.

De ahí salen las tres salidas honestas. La primera es no tener agujeros: si tus datos son una secuencia, usa table.insert y table.remove, que la mantienen íntegra, y el operador te dirá siempre la verdad. La segunda es llevar la cuenta explícita, exactamente como hace table.pack, que devuelve una tabla con un campo n fiable precisamente porque los argumentos variádicos pueden contener nil. La tercera es definir __len en la metatabla cuando construyes un tipo propio, que desde Lua 5.2 se respeta también para tablas y te permite imponer la semántica que tu abstracción necesite.