Почему оператор длины Lua (#) возвращает неожиданные значения?

Lua имеет оператор # для вычисления "длины" таблицы, используемой в качестве массива. Я проверил этого оператора, и я удивлен.

Это код, который я запускаю под 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?

Может кто-нибудь объяснить правила?

Ответ 1

Цитирование справочника Lua 5.2:

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

Результатом оператора # на непостоянствах является undefined. Но что происходит в реализации C Lua, когда мы вызываем # на непоследовательность?

Фон: Таблицы в Lua внутренне разделены на часть массива и хэш-часть. Это оптимизация. Lua пытается избежать выделения памяти часто, поэтому он предварительно выделяет для следующей мощности два. Это еще одна оптимизация.

Когда последним элементом в массиве является nil, результат # - это длина кратчайшей допустимой последовательности, найденной путем binsearching части массива для первого ключа nil-follow.
Когда последний элемент в массиве не является nil И хэш-часть пуста, результатом # является физическая длина части массива.
Когда последний элемент в массиве не является nil И хэш-часть НЕ пуста, результатом # является длина самой короткой допустимой последовательности, найденной путем бинарного поиска хэш-части для первого nil- (это такое положительное целое число i, что t[i] ~= nil и t[i+1] == nil), считая, что часть массива заполнена не-нильскими (!).

Таким образом, результат # - это почти всегда (желаемая) длина кратчайшей допустимой последовательности, если последний элемент в массиве, представляющий не-последовательность, не равен нулю. Затем результат больше желаемого.

Почему? Похоже, что еще одна оптимизация (для массивов с мощностью-два). Сложность # в таких таблицах O(1), а другие варианты O(log(n)).