Luaにおける表取長さ深さ解析

作者:バカカタツムリリンク:https://www.jianshu.com/p/1e8ab8fe55e4出典:簡書
長さをとる関数

    /*
    ** 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は毎回2倍に拡大し、t[j]は空ではなく、t[2*j]は空であり、その後、二分法によって検索し、最終的な値を見つけた.
≪インスタンス｜Instance｜emdw≫
例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つ目は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)配列やハッシュバケツ部分を1つのテーブルに混用しないようにし,1つのテーブルに1種類のデータしか格納しないことが望ましい.luaの実現には確かに両者の統一表現の遍歴が提供されているが,これは利用者がこの2つの方式を混用すべきであることを意味するものではない.(2)nil値をできるだけテーブルに格納しないようにすると,長さ取り操作の挙動が不安定になる.(3)この操作のコストが大きいため,このlua解釈器の背後にある動作を予め割り当て,配列部分のみを用いるなどの戦略により回避することで,多くの効率を向上させることができる.