Lua

Lua之table长度求解

2018-09-15  本文已影响0人  糊涂小蜗牛

取长度使用到的函数

    /*
    ** Try to find a boundary in table 't'. A 'boundary' is an integer index
    ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
    */
    lua_Unsigned luaH_getn (Table *t) {
      unsigned int j = t->sizearray;
      if (j > 0 && ttisnil(&t->array[j - 1])) { // 数组最后一个元素为空,二分法查找
        /* there is a boundary in the array part: (binary) search for it */
        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 must find a boundary in hash part */
      else if (isdummy(t))  /* hash part is empty? */ // 数组最后一个元素不为空,但是 hash 部分为空
        return j;  /* that is easy... */
      else return unbound_search(t, j); // 数组最后一个元素不为空,hash 部分也不为空
    }
/*
    首先判断的是,数组最后一个元素是否为空
        为空
            二分法查找
        不为空,但 hash 部分为空
            返回数组长度作为要获取的长度
        不为空,hash 也不为空
            unbound_search(t, j),实现如下
*/
    static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) {
      lua_Unsigned i = j;  /* i is zero or a present index */
      j++;
      /* find 'i' and 'j' such that i is present and j is not */
      while (!ttisnil(luaH_getint(t, j))) { // 找到 t[j] 不为空, t[2*j] 为空,那么长度在 j 与 2*j 之间
        i = j;
        if (j > l_castS2U(LUA_MAXINTEGER) / 2) {  /* overflow? */
          /* table was built with bad purposes: resort to linear search */
          i = 1;
          while (!ttisnil(luaH_getint(t, i))) i++;
          return i - 1;
        }
        j *= 2;
      }
      /* now do a binary search between them */
      while (j - i > 1) { 
        lua_Unsigned m = (i+j)/2; // 二分法查找
        if (ttisnil(luaH_getint(t, m))) j = m;
        else i = m;
      }
      return i;
    }

数组的长度为 j,hash 部分从 j+1 开始遍历,j 每次扩大两倍,找到t[j] 不为空, t[2*j] 为空,然后通过二分法查找,找到最终的值。

实例

例1 (全部为数组部分)

    local t = {1, 2, 3, 4}
    print(#t)   -- 4

解释:t 没有 hash 部分,数组长度为4。t[4] 不为空,所以返回 j = 4

例2

    local t = {1, nil, 3}
    print(#t)   -- 3

解释:t没有 hash 部分,数组长度为3。t[3] 不为空,所以返回 j = 3

例3

    local t = {1, nil, 3, nil}
    print(#t)   -- 1

解释:t 没有 hash 部分,数组长度为4。t[4] 为空,所以利用二分法查找

    i = 0, j = 4, m = (i+j)/2 = 2, array[2] 为空, j = m = 2;
    i = 0, j = 2, m = (i+j)/2 = 1, array[1] 不为空, i = m = 1;
    i = 1, j = 2, 条件 j - i > 1 不满足,循环终止,返回 i = 1。

例4(全部为 hash 部分)

    local t = {[1] = 1, [3] = 3, [5] = 5, [6] = 6, [7] = 7}     
    print(#t)   -- 1

解释:t没有数组元素。调用 unbound_search 函数,hash 部分从 j = 1 开始遍历,其中 i记录的是上一个 j的值

    i = 0, j = 1, t[1] 不为空, i = j = 1, j = 2
    i = 1, j = 2, t[1] 为空, j - i = 1 > 1 不成立,返回 i = 1。

例5

    local t = {[1] = 1, [2] = 2, [4] = 4, [6] = 6}  
    print(#t)   -- 6

解释:t没有数组元素,调用 unbound_search 函数,hash 部分从 j = 1 开始遍历

    i = 0, j = 1, t[1] 不为空, i = j = 1, j = 2
    i = 1, j = 2, t[2] 不为空, i = j = 2, j = 4
    i = 2, j = 4, t[4] 不为空, i = j = 4, j = 8
    i = 4, j = 8, t[8] 为空, j - i = 4 > 1 成立,通过二分法查找值

    i = 4, j = 8, m = (i+j)/2 = 6, t[6] 不为 nil, i = m = 6;
    i = 6, j = 8, m = (i+j)/2 = 7, t[7] 为 nil, j = m = 7;
    i = 6, j = 7, 条件 j - i > 1 不满足,循环终止,返回 i = 6。

例6(既包含数组部分,包含hash 部分)

    local t = {1, 2, 3, [5] = 5}
    print(#t)   -- 3

解释:数组部分长度为3,hash 部分长度为1。由于 t[3] 不为空,同时 hash 部分不为空,所以调用 unbound_search 函数,hash 部分从 j = 4 开始遍历

    i = 3, j = 4, t[4] 为空, j - i = 1 > 1 不成立,返回 i = 3

例7

    local t = {1, 2, 3, [4] = 4}
    print(#t)   -- 4

解释:数组部分长度为3,hash 部分长度为1。由于 t[3] 不为空,同时 hash 部分不为空,所以调用 unbound_search 函数,hash 部分从 j = 4 开始遍历

    i = 3, j = 4, t[4] 不为空, i = j = 4, j = 8
    i = 4, j = 8, t[8] 为空, j - i = 4 > 1 成立
    通过二分法查找,最终返回 i = 4

例8

   local t = {1, 2, 3, nil, [5] = 5}
   print(#t)   -- 3

解释:数组部分长度为4,hash 部分长度为1。由于 t[4] 为空,则在数组部分利用二分法查找,参考例3,最终返回 i = 3

以上都是在创建 table 时确定好了数组部分和 hash 部分,但是如果新增键值的话,可能会造成调用 rehash 函数,重新分配数组和 hash 部分。

例9

    local t = {1, [4] = 4}
    print(#t)   -- 1
    t[3] = 3    -- 添加键值
    print(#t)   -- 4

第一个为1,可以参考上面的例子,当添加键值的时候,重新分配,结果是数组部分长度为4,hash 部分为0,等价于

 local t = {1, nil, 3, 4}

参考Lua之table新增整数键值。由于数组部分 t[4]不为空,返回 i = 4

例10

    local t = {1, [5] = 5}
    t[3] = 3
    print(#t)   -- 1

当添加键值的时候,重新分配,结果是数组部分长度为1,hash 部分为2,等价于

 local t = {1, [3] = 3, [5] = 5}

例11

    local t = {1, 2,  [5] = 5}
    t[4] = 4
    print(#t) -- 5
等价于
    local t = {1, 2, nil, 4, [5] = 5}

总结
(1)尽量不要在一个表中混用数组或散列桶部分,即一个表最好只存放一类数据。lua的实现上确实提供了两者统一表示的遍历,但是这并不意味着使用者就应该混用这两种方式。
(2)尽量不要在表中存放nil值,这会让取长度操作的行为不稳定。
(3)尽量避免重新散列操作,因为这个操作的代价极大,通过预分配、只使用数组部分等策略规避这个lua解释器背后的动作,能提升不少效率。

上一篇下一篇

猜你喜欢

热点阅读