8

我是 Lua 的新手,这些天我正在学习 table 的用法。从tutorials我知道Lua对数字索引项和非数字索引项的处理是不同的,所以我自己做了一些测试,今天我发现了一个有趣的现象,我无法解释:

编码

t = {1, 2, 3, a='a', b='b'}
print(#t)

得到

3

因为#操作员只计算数字索引项。然后我测试了以下代码

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,200 do
    t[i] = i
end
print(#t)

我明白了

3
3

到目前为止,我认为 Lua 将后来添加的那些不连续项视为非数字索引项。但是,在我稍微更改代码之后

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,300 do
    t[i] = i
end
print(#t)

我明白了

3
300

我对这种现象感到困惑,有人知道原因吗?谢谢。

(此现象可在http://www.lua.org/cgi-bin/demo重现)

更新:

我试过这段代码

t = {1, 2, 3, a='a', b='b'}
print(#t)

for i = 100,300 do
    t[i] = i
    print("add", i, #t)
end

for i = 100,300 do
    t[i] = nil
    print("del", i, #t)
end

我明白了

3
add 100 3
add 101 3
add 102 3
...
add 223 3
add 224 3
add 225 3
add 226 226
add 227 227
add 228 228
...
add 298 298
add 299 299
add 300 300
del 100 300
del 101 300
del 102 300
...
del 253 300
del 254 300
del 255 300
del 256 3
del 257 3
del 258 3
...
del 298 3
del 299 3
del 300 3

这个例子表明 Lua 确实在稀疏和密集之间转换了一个表。

4

2 回答 2

10

我还没有查看#操作符是如何实现的,但我敢打赌,通过添加额外的 100 个索引,你已经使范围1-300变得足够密集,以至于索引100-300最终出现在“数组”部分表实现而不是“哈希”部分。

更新:

好的,我查看了原始表长度的来源。如果数组部分的最后一项是 nil,它会二进制搜索数组以找到最低的“边界”(非 nil 索引后跟 nil 索引)。如果它不是 nil,它决定边界必须在散列中并搜索它。

因此,对于包含数字索引的表{1, 2, 3, 100..200},我认为它不够密集,并且数组部分仅包含{1, 2, 3}. 但是对于包含 的表格{1, 2, 3, 100..300},它可能足够密集,以至于数组部分在该100..300部分内的某个位置结束(我认为数组部分始终是 2 的幂,所以它不可能以 结束300,但我不是 100% 肯定的) .

更新 2:

当一个 lua 表被重新散列时,它会计算整数键的数量。然后它遍历不超过整数键数量两倍的所有 2 的幂,并找到至少 50% 密集的 2 的最大幂(这意味着如果数组部分这么大,至少 50%所有值都不是零)。

因此{1, 2, 3, 100..200},它向上走

1: 100% dense; good
2: 100% dense; good
4: 75% dense; bad
8: 37.5% dense; bad
16: 18.75% dense; bad
32: 9.375% dense; bad
64: 4.6875% dense; bad
128: 25% dense; bad
256: 40.625% dense; bad

最好的值是 2,所以它最终的数组大小为 2。因为2它不是 nil,所以它在哈希中搜索边界并找到3.

添加201..300后,最后一步变为

256: 62.5% dense; good

这导致数组部分覆盖1..256,并且由于256非零,它再次搜索散列中的边界并获得 300`。


最后,Lua 5.2 将“序列”定义为一个表,其中包含从 1 开始且没有孔的唯一整数键。它定义#为仅对序列有效。通过这种方式,Lua 可以摆脱您注意到的在整数序列中有孔的表的奇怪行为。

于 2013-04-18T06:59:19.780 回答
5

表 t 的长度仅在表是序列时才定义,也就是说,对于某个整数 n,其正数字键的集合等于 {1..n}。

于 2013-04-18T07:11:12.680 回答