Lua 5.1#运算符和字符串比较(性能)

Question

为了这:

b = #{1,2,3}
c = 'deadbeef' == 'deadbabe'

b是以O(n)还是O(1)计算的？在什么情况下？行为是否一致,或者像稀疏数组行为一样依赖于上下文？是字符串比较O(1)还是O(n)？我知道字符串是不可变的,Lua比较哈希值但是如果2个不同的字符串哈希到相同的值呢？请不要回答"不要担心低级行为,儿子".我对低级行为感兴趣.谢谢.

编辑

3)#的结果是存储在某个地方,还是每次我为同一个数组调用它时计算出来的？

Answer 1

表的长度计算在O(log n).算法大致如下:

• 尝试nil通过采取步骤找到映射到的一些整数索引.步长每次加倍.(如果nil在数组部分的末尾找到一个值,则可以跳过此部分.)
• 当找到这样的索引时,在该索引与最后一个已知非nil索引之间的间隔上使用分而治之算法,以找到nil直接后跟值的非nil值.

在这里查看详细信息.如果您具有连续的值序列,则此算法很有效,但如果阵列之间有孔,则会产生意外结果.

编辑:内置#运算符的结果未缓存,因此上述算法每次#在表上使用时都会运行(不使用__lenmetamethod).

关于字符串比较(用于相等):较新的Lua版本在内部有两种类型的字符串:短字符串(通常最多40个字节)和长字符串.使用长字符串进行比较memcmp(如果长度匹配),所以你得到O(n).另一方面,短字符串是"interned",这意味着当您在Lua中创建某个短字符串时,将检查是否已存在具有相同内容的字符串.如果是这样,则重用旧的字符串对象,并且不分配新的字符串.这意味着您可以简单地比较内存地址以检查短字符串是否相等,即O(1).