Perché l'operatore di lunghezza (#) di Lua restituisce valori imprevisti?

Question

Lua ha l'operatore # per calcolare la "lunghezza" di una tabella utilizzata come matrice. Ho controllato questo operatore e sono sorpreso.

Questo è un codice, che ho lasciato correre sotto Lua 5.2.3:

t = {}; 
t[0] = 1; 
t[1] = 2; 
print(#t); -- 1 aha lua counts from one 
t[2] = 3; 
print(#t); -- 2 tree values, but only two are count 
t[4] = 3; 
print(#t); -- 4 but 3 is mssing? 
t[400] = 400; 
t[401] = 401; 
print(#t); -- still 4, now I am confused? 


t2 = {10, 20, nil, 40} 
print(#t2); -- 4 but documentations says this is not a sequence? 

qualcuno può spiegare le regole?

Answer 1

Citando il Lua manuale 5.2 Riferimento:

the length of a table t is only defined if the table is a sequence, that is, the set of its positive numeric keys is equal to {1..n} 
for some integer n 

Il risultato # operatore non è sequenze indefinito. Ma what happens in C implementation of Lua when we call # on a non-sequence?

Sfondo: le tabelle in Lua sono suddivise internamente in parti di serie e parti di hash. Questa è un'ottimizzazione. Lua cerca di evitare di allocare spesso la memoria, quindi preassegna per la prossima potenza di due. Questa è un'altra ottimizzazione.

1. Quando l'ultimo elemento della matrice è parte nil, il risultato della # è la lunghezza più breve sequenza valida trovato dai binsearching parte matrice per la prima chiave nil-seguito.
2. Quando l'ultimo elemento nella parte dell'array non è nil E la parte hash è vuota, il risultato di # è la lunghezza fisica della parte dell'array.
3. Quando l'ultimo elemento nella parte dell'array non è nil E la parte hash NON è vuota, il risultato di # è la lunghezza della sequenza valida più breve trovata da binsearching della parte hash per la prima chiave seguita da zero (quella è un numero intero positivo i che t[i] ~= nil e t[i+1] == nil), presupponendo che la parte dell'array sia piena di non-nils (!).

Così il risultato di # è quasi sempre la (desiderato) lunghezza del minimo sequenza valida, a meno che l'ultimo elemento della parte matrice che rappresenta un non-sequenza è non-zero. Quindi, il risultato è più grande di di quanto desiderato.

Perché è quello? Sembra ancora un'altra ottimizzazione (per matrici power-of-two). La complessità di # su tali tabelle è O(1), mentre altre varianti sono O(log(n)).