作者:婕小米 | 来源:互联网 | 2023-06-08 12:57
篇首语:本文由编程笔记#小编为大家整理,主要介绍了Lua中table长度到底是怎么来的相关的知识,希望对你有一定的参考价值。 节前上班时同事在工作群里发了一张图,并感叹lua的table的长度真是诡异
篇首语:本文由编程笔记#小编为大家整理,主要介绍了Lua中table长度到底是怎么来的相关的知识,希望对你有一定的参考价值。
节前上班时同事在工作群里发了一张图,并感叹lua的table的长度真是诡异。
↑乍一看似乎莫名其妙的长度
乍一看归结为不从1开始并顺序[k] = v 形式插入表的都已hash表形式存储,那么table的长度则不可预估这样简单粗暴的下了定论。
后来等工作空闲下来的时候,和另一位同事仔细过了一遍lua的源码和解析,终于明白事情并非那么简单,于是便有了今天这篇文章总结一下。
table的数据结构
typedef union TKey {
struct {
TValuefields;
struct Node *next;
} nk;
TValue tvk;
} TKey;
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
typedef struct Table {
CommonHeader;
lu_byte flags;
lu_byte lsizenode;
struct Table *metatable;
TValue *array;
Node *node;
Node *lastfree;
GCObject *gclist;
int sizearray;
} Table;
由这部分源码我们可以知道table的数据是由两部分组成:
table的#如何取得的
首先我们找到#取表长度的源码进行分析
int luaH_getn (Table *t) {
unsigned int j = t->sizearray;
if (j > 0 && ttisnil(&t->array[j - 1])) {
unsigned int i = 0;
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(&t->array[m - 1])) j = m;
else i = m;
}
return i;
}
else if (t->node == dummynode)
return j;
else return unbound_search(t, j);
}
static int unbound_search (Table *t, unsigned int j) {
unsigned int i = j;
j++;
while (!ttisnil(luaH_getnum(t, j))) {
i = j;
j *= 2;
if (j > cast(unsigned int, MAX_INT)) {
i = 1;
while (!ttisnil(luaH_getnum(t, i))) i++;
return i - 1;
}
}
while (j - i > 1) {
unsigned int m = (i+j)/2;
if (ttisnil(luaH_getnum(t, m))) j = m;
else i = m;
}
return i;
}
阅读源码结合注释,我们可以明白取长度时函数会在数组部分不为空且最后一个元素不为nil时尝试在数组部分进行二分法查找一个index,这个index需要满足t[index]不为nil而t[index+1]为nil的。
函数的三个分支分别为
table的数组长度大于0且最后一个取出表数组长度的的元素为nil
table的哈希部分为空(那么数组长度就是表长度)
其他情况(进入下面的 unbound_search 来在哈希部分查找长度)
在对哈希部分查找长度时,进行边界扩大搜索,每次扩大为之前的二倍,再使用二分法进行查找number与nil的分界元素。
此时我们可以做一个小小的验证
local t1 = {1,2,3,4,5}
print("t1的长度为:",
t1[7] = 7
print("t1的长度为:",
t1[9] = 9
print("t1的长度为:",
print("---------------------")
local t2 = {1,2,3,4,5}
print("t2的长度为:",
t2[8] = 8
print("t2的长度为:",
t2[9] = 9
print("t2的长度为:",
t1的长度为:5
t1的长度为:5
t1的长度为:5
---------------------
t2的长度为:5
t2的长度为:8
t2的长度为:9
我们可以看到t1在luaH_getn 的第一次打印中,sizearray 为8,但t[8]为nil,此时进入第一个分支进行二分法查找最终返回5,在第二次打印中依然t[8]为nil,此时依然返回5,第三次打印同理,一直在第一个逻辑分支中。
而t2在第一次打印中同上,第二次打印时,t[8]有值了,此时满足第二个分支即哈希表部分为空,表长度等于sizearray 为8。第三次打印sizearray 依然为8,进入第三个分支,即此时进入unbound_search 来查找表长度。此时先找到t2[9]不为nil,将j *= 2 翻倍为18,于是在9-18范围进行二分查找t[index]不为nil但t[index + 1]为nil的值,最终返回t[9]。
对于二分查找法虽然效率很高,但会存在不精确的问题。在二分临界值附近会出现极大的区别,也就是我在文章开头提到的情况。
local a = {}
for i = 5,12 do a[i] = i end
print("a的长度为:",
print("---------------------")
local b = {}
for i = 5,13 do b[i] = i end
print("b的长度为:",
a的长度为:0
---------------------
b的长度为:13
数组长度为什么是0
细心的朋友们一定发现了上面的例子似乎和我们讲的有些不太一样,为什么a的长度会变成0了呢?这里我们就不得不再去了解一下lua 给table赋值的两种方式。
显然我们的a表与b表没有使用初始化长度的方式来进行赋值。那么对于a,b两表,在赋值的过程中会不断的填充元素,导致表空间不足需要动态扩充。
static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
Node *mp = mainposition(t, key);
if (!ttisnil(gval(mp)) || mp == dummynode) {
Node *othern;
Node *n = getfreepos(t);
if (n == NULL) {
rehash(L, t, key);
return luaH_set(L, t, key);
}
lua_assert(n != dummynode);
othern = mainposition(t, key2tval(mp));
if (othern != mp) {
while (gnext(othern) != mp) othern = gnext(othern);
gnext(othern) = n;
*n = *mp;
gnext(mp) = NULL;
setnilvalue(gval(mp));
}
else {
gnext(n) = gnext(mp);
gnext(mp) = n;
mp = n;
}
}
gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
luaC_barriert(L, t, key);
lua_assert(ttisnil(gval(mp)));
return gval(mp);
}
在扩充的过程中会调用rehash 操作进行重新分配数组与哈希表的内存空间。
static void rehash (lua_State *L, Table *t, const TValue *ek) {
int nasize, na;
int nums[MAXBITS+1];
int i;
int totaluse;
for (i=0; i<=MAXBITS; i++) nums[i] = 0;
nasize = numusearray(t, nums);
totaluse = nasize;
totaluse += numusehash(t, nums, &nasize);
nasize += countint(ek, nums);
totaluse++;
na = computesizes(nums, &nasize);
resize(L, t, nasize, totaluse - na);
}
static int computesizes (int nums[], int *narray) {
int i;
int twotoi;
int a = 0;
int na = 0;
int n = 0;
for (i = 0, twotoi = 1; twotoi/2 <*narray; i++, twotoi *= 2) {
if (nums[i] > 0) {
a += nums[i];
if (a > twotoi/2) {
n = twotoi;
na = a;
}
}
if (a == *narray) break;
}
*narray = n;
lua_assert(*narray/2 <= na && na <= *narray);
return na;
}
rehash 操作会调用computesizes 来统计数组部分不为nil的元素个数来计算最终要分配的空间长度。
对于表a来讲,在for循环插入元素时,不断进入computesizes 试图扩充数组长度,数组长度在1->2->4->8->16的过程中没有满足一个重要的条件,即if (a > twotoi/2) /* more than half elements present? */ 数组重新分配长度的原则在于数组利用效率高于50%。那么可以很容易的知道了为什么a表的sizearray 为0,而b表的sizearray 一下变成了13。
至此,文章开头的问题也有了完整的答案。