Lua表的一个有趣现象

8

我是一名Lua的新手,最近在学习有关表格的使用。从教程中我知道Lua会对数值索引和非数值索引的项进行不同的处理,所以我自己做了一些测试。今天我发现了一个有趣的现象,但是我无法解释它:

这是代码:

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

gets

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可以在稀疏表和密集表之间进行转换。

请先阅读文档和@Egor的答案。如果您真正对实现特定的细节,尤其是未定义的行为感兴趣,请切换到测试和阅读源代码。 - Tom Blodget
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处结束,但我不确定)。
更新2:
当Lua表重新哈希时,它会计算整数键的数量。然后,它将沿着不超过两倍于整数键数量的所有2的幂次方行走,并找到至少50%密集的最大2的幂次方(这意味着如果数组部分这么大,至少50%的所有值将为非nil)。
因此,对于{1, 2, 3, 100..200},它沿着数组大小为2、4、8、16等行走。
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不为nil,它再次搜索哈希中的边界并获取300。


最终,Lua 5.2 将“序列”定义为仅具有从1开始没有空洞的整数键的表,并将#仅定义为序列有效。这样Lua就可以处理整数序列中存在空洞的表格的奇怪行为。


是的,看起来是这样。但我想知道Lua如何判断密度。我还没有找到任何在线文档提到这一点。 - SaltyEgg
非常感谢您的努力!但是现在我有一个关于效率的问题:如果一个人不断地编辑表格,它可能会在稀疏和密集之间跳转,并且Lua可能会频繁进行转换。这会减慢程序的速度吗? - SaltyEgg
1
@SaltyEgg:只有在数组或哈希表中找不到放置新键的位置时,它才会重新散列。因此,重新散列并不是特别频繁的操作。请注意,由于它必须重新分配数组和哈希表中的一个或两个,这意味着将所有值复制到新存储空间中,因此执行此计算并不是非常繁琐的操作。 - Lily Ballard
4
有趣的研究!但是这种行为非常依赖于具体实现。例如,LuaJIT在相同的表上使用#运算符会给出另一个值。 - Egor Skriptunoff
@KevinBallard:是的,我非常感兴趣了解Lua的实现方式。Lua使用表来表示数组和字典,所以我进行了这些测试,以便找出背后的原因。 - SaltyEgg
显示剩余2条评论

5

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


但是我发现当一个间隔[1,n]足够密集时,表格就变成了一个序列(我还做了其他测试,table.removetable.insert在密集表上有效,但不在稀疏表上)。 - SaltyEgg
2
@SaltyEgg:Egor 的说法在技术上是正确的。Lua 5.2 将“序列”定义为一个仅包含从1开始的整数键且整数序列中没有洞的表格。而 # 运算符仅适用于序列。 - Lily Ballard

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接