Tại sao toán tử độ dài (#) của Lua trả về giá trị không mong muốn?

Question

Lua có toán tử # để tính toán độ dài "" của bảng đang được sử dụng làm mảng. Tôi đã kiểm tra toán tử này và tôi rất ngạc nhiên.

Đây là mã, rằng tôi hãy để chạy theo 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? 

Ai đó có thể giải thích các quy tắc?

Answer 1

trích dẫn 5.2 Reference Manual Lua:

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 

Kết quả của # điều hành trên phi trình tự là không xác định. Nhưng what happens in C implementation of Lua when we call # on a non-sequence?

Bối cảnh: Các bảng trong Lua được chia nội bộ thành phần mảng và phần băm. Đó là một tối ưu hóa. Lua cố gắng tránh phân bổ bộ nhớ thường xuyên, do đó, nó phân bổ trước cho sức mạnh tiếp theo của hai. Đó là một tối ưu hóa khác.

1. Khi mục cuối cùng trong phần mảng là nil, kết quả của # là chiều dài của chuỗi giá trị ngắn nhất được tìm thấy bởi binsearching phần mảng cho phím nil-tiếp đầu tiên.
2. Khi mục cuối cùng trong phần mảng không phải là nil VÀ phần băm rỗng, kết quả của # là độ dài vật lý của phần mảng.
3. Khi mục cuối cùng trong phần mảng không phải là nil VÀ phần băm KHÔNG trống, kết quả của # là độ dài của chuỗi hợp lệ ngắn nhất được tìm thấy bởi binsearching phần băm cho khóa đầu tiên không được theo dõi (là số nguyên dương như vậy i rằng t[i] ~= nil và t[i+1] == nil), giả sử rằng phần mảng có đầy không phải là nils (!).

Vì vậy, kết quả của # là gần luôn (mong muốn) chiều dài của chuỗi giá trị ngắn nhất, trừ yếu tố cuối cùng ở phần mảng đại diện cho một tổ chức phi chuỗi là phi nil. Sau đó, kết quả là lớn hơn so với mong muốn.

Tại sao lại như vậy? Nó có vẻ như nhưng tối ưu hóa khác (đối với các mảng có kích thước bằng hai). Độ phức tạp của # trên các bảng như vậy là O(1), trong khi các biến thể khác là O(log(n)).