Lua的表格的一个有趣现象

2013-4-18 7:48:8
收藏：0
阅读：98
评论：2

我是 Lua 的新手，最近学习表的用法。从教程中我知道 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 确实会将表在稀疏和稠密之间转换。

点赞
用户582
用户582

我没有查看 # 运算符的实现方式，但我认为加上额外的 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 表重新哈希时，它会计算整数键的数量。然后它遍历所有小于整数键两倍的二的幂，并找到最大的 50% 密集度的二的幂（意思是，如果数组部分这么大，至少 50% 的所有值将非空）。

因此，用于 {1，2，3，100..200} 的数组为

1: 100% 密集度; 好
2: 100% 密集度; 好
4: 75% 密集度; 坏
8: 37.5% 密集度; 坏
16: 18.75% 密集度; 坏
32: 9.375% 密集度; 坏
64: 4.6875% 密集度; 坏
128: 25% 密集度; 坏
256: 40.625% 密集度; 坏

最好的值是 2，因此它的数组大小为 2。由于 2 是非 nil 的，因此它在哈希中搜索边界并找到 3。

一旦添加了 201..300，则最后一步变成了

256: 62.5% 密集度; 好

这导致数组部分覆盖了 1..256，由于 256 是非 nil 的，它再次在哈希中搜索边界，并得到 300。

最终，Lua 5.2 将 "序列" 定义为具有从 1 开始并且不带空洞的仅积分键的表。并将 # 定义为仅对序列有效。这样，Lua 可以处理整数序列中存在空洞的表的怪异行为。

2013-04-18 06:59:19
用户1847592
用户1847592

如果表格是一个序列，即其正数数字键的集合等于某个整数 n 的 {1..n}，则表格 t 的长度才有定义。

2013-04-18 07:11:12

作者:

用户2251866

用户2251866
推荐文章