卢阿桌子的有趣现象 [英] An Interesting phenomenon of Lua's table

问题描述

我是Lua的新手，最近我正在学习表的用法.从教程中我知道Lua对数字索引项和非数字索引项的处理方式有所不同，因此我自己进行了一些测试，今天我发现了一个有趣的现象，无法解释:

I'm new to Lua, and I'm learning the usage of table these days. From tutorials I know that Lua treats numeric indexed items and non-numeric indexed items differently, so I did some tests myself, and today I found an interesting phenomenon and I can't explain it:

代码

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

获取

3

因为#运算符仅计算数字索引项.然后我测试了以下代码

because the # operator counts numeric indexed items only. Then I tested the following code

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

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

我知道

3
3

到现在为止，我认为Lua会将后来添加的不连续项视为非数字索引项.但是，在我更改了代码后

Till now I think Lua treats those discontinuous items added later as non-numeric indexed ones. However, after I change the code a little bit

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

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

我知道

3
300

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

I'm confused by this phenomenon, does anyone know the reason? Thanks.

(此现象可以在 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确实在稀疏表和密集表之间转换了表.

This example shows that Lua does convert a table between sparse and dense.

推荐答案

我没有研究#运算符的实现方式，但是我敢打赌，通过添加额外的100个索引，您已经导致范围1-300变得足够密集，以至于索引100-300最终出现在表实现的数组"部分而不是哈希"部分.

I haven't looked at how the # operator is implemented, but I bet what's going on is that by adding the extra 100 indexes, you've caused the range 1-300 to become dense enough that the indexes 100-300 end up in the "array" part of the table implementation instead of the "hash" part.

更新:

好吧，我查看了原始表长度的来源.如果数组部分中的最后一项为nil，则对数组进行二进制搜索以找到最低的边界"(非nil索引，后跟nil索引).如果它不是nil，则确定边界必须在哈希中并进行搜索.

Ok, I looked at the source for the primitive table length. If the final entry in the array part is nil, it binary-searches the array to find the lowest "boundary" (a non-nil index followed by a nil index). If it's not nil, it decides the boundary must be in the hash and searches for it.

因此，对于包含数字索引{1, 2, 3, 100..200}的表，我认为它不够密集，并且数组部分仅包含{1, 2, 3}.但是使用包含{1, 2, 3, 100..300}的表，它的密度可能足够大，以至于数组部分在100..300部分内的某个位置结束(我认为数组部分始终是2的幂，因此它不可能以300结尾，但我不是100％积极).

So with the table containing numeric indexes {1, 2, 3, 100..200}, I assume it's not dense enough and the array part only contains {1, 2, 3}. But with the table containing {1, 2, 3, 100..300}, it's presumably dense enough that the array part ends somewhere within the 100..300 part (I think the array part is always a power of 2, so it can't possibly end at 300, but I'm not 100% positive).

更新2:

重新创建lua表时，它会计算整数键的数量.然后，它遍历两个不超过整数键数量两倍的所有幂，并找到两个密度至少为50％的最大幂(这意味着如果数组部分这么大，则至少为50％)所有值都将为非零).

When a lua table is rehashed, it counts the number of integer keys. It then walks up all the powers of two that are no more than twice the number of integral keys, and finds the largest power of two that is at least 50% dense (meaning that if the array part were this large, at least 50% of all values would be non-nil).

因此，使用{1, 2, 3, 100..200}，它就会走动

So with {1, 2, 3, 100..200}, it walks up

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.

The best good value is 2, so it ends up with an array size of 2. Since 2 is non-nil, it searches the hash for the boundary and finds 3.

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

256: 62.5% dense; good

导致数组部分覆盖1..256，并且由于256不为nil，它再次在哈希中搜索边界并获得300`.

which causes the array part to cover 1..256, and since 256 is non-nil, it again searches for the boundary in the hash and gets 300`.

最后，Lua 5.2将序列"定义为一个表，表中的唯一整数键从1开始，一直向上无孔.并且它将#定义为仅对序列有效.通过这种方式，Lua可以摆脱您在积分顺序中有孔的表中注意到的怪异行为.

In the end, Lua 5.2 defines a "sequence" as a table with exclusively integral keys starting at 1 and going up with no holes. And it defines # as only being valid for sequences. This way Lua can get away with the weird behavior you noticed for tables that have holes in their integral sequences.

这篇关于卢阿桌子的有趣现象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！