6

Lua和Python：实现一个高效的List对象(2)

 3 years ago
source link: https://zhuanlan.zhihu.com/p/180076604
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Lua和Python：实现一个高效的List对象(2)

接上回所说的来实现一个list对象，其结构如下：

typedef struct refdata_t {
    int ref;            // 对Table元素的引用
    int key;            // 后面再说。。。
} refdata_t;

typedef struct list_t {
    int cap;            // 数组容量
    int size;           // 当前数组大小
    int ref;            // 当前引用，稍后讲解
    refdata_t *ary;     // 数组数据
} list_t;

list_t是一个userdata，里面的字段是实现数组必须的一些信息。refdata_t是数组的元素结构，现在不管ref和key是干啥的，我们先看看这个userdata是怎么创建的：

#define LIST_MT "CO_LIST_MT"

// list.new([cap]) -> ud
static int list_new(lua_State *L) {
    int cap = (int)luaL_optinteger(L, 1, 4);
    luaL_argcheck(L, cap > 0, 1, "invalid size");
    list_t *ls = (list_t*)lua_newuserdata(L, sizeof(list_t));           // 创建userdata，数据是list_t
    ls->cap = cap;
    ls->size = 0;
    ls->ref = 0;
    ls->ary = (refdata_t*)malloc(ls->cap * sizeof(refdata_t));          // 创建list_t的数组
    luaL_setmetatable(L, LIST_MT);      // <ud>                         // 为list_t指定元表，后面再说
    lua_createtable(L, ls->cap, 0);     // <ud|tab>                     // 创建一个table，并关联到list_t
    lua_setuservalue(L, -2);            // <ud>
    return 1;
}

userdata是可以关联Lua值的，这一点对list尤其重要，我们创建了一个Table，并把它关联给list，真正的数组元素就存在这个Table中，而list的数组保存的是Table元素的“引用”，我们抽象为refdata_t结构，其实真正用到的只是refdata_t.ref，里面的key是干什么的？这里先卖个关子，以后就会知道。

那怎么引用呢，luaL_ref/luaL_unref这对API正是我们需要的，关于它们的用法，可看下我的另一篇文章深入Lua：引用机制：

  • 调用luaL_ref(tab, obj) -> ref，之后，把obj设置给tab，同时返回一个ref，以后通过tab[ref]即可得到obj。
  • 调用luaL_unref(tab, ref)之后，相当于tab[ref]=nil`，把obj从tab删除，并把ref回收，留待下次重用。

不过luaL_ref/luaL_unref仍然存在一个性能问题，它通过lua_rawlen得到一直增长的引用值，这个函数最终还是调用luaH_getn去取表的长度，极有可能需要O(log n)的复杂度。我们仿照这对API实现两个函数，不同的是在list_t里面记了一个ref字段，这个字段其实就是表的长度，这样就不必通过lua_rawlen去取长度了：

#define freelist    0

int ref_value(lua_State *L, list_t *ls, int t) {
    int ref;
    t = lua_absindex(L, t);
    lua_rawgeti(L, t, freelist);     /* get first free element */
    ref = (int)lua_tointeger(L, -1); /* ref = t[freelist] */
    lua_pop(L, 1);                   /* remove it from stack */
    if (ref != 0) {                  /* any free element? */
        lua_rawgeti(L, t, ref);      /* remove it from list */
        lua_rawseti(L, t, freelist); /* (t[freelist] = t[ref]) */
    }
    else                 /* no free elements */
        ref = ++ls->ref; /* get a new reference */      // 这里增长引用
    lua_rawseti(L, t, ref);
    return ref;
}

void unref_value(lua_State* L, int t, int ref) {
    if (ref >= 0) {
        t = lua_absindex(L, t);
        lua_rawgeti(L, t, freelist);
        lua_rawseti(L, t, ref); /* t[ref] = t[freelist] */
        lua_pushinteger(L, ref);
        lua_rawseti(L, t, freelist); /* t[freelist] = ref */
    }
}

别小看这个改动，实测中因为这个有了可观的性能提升。

现在已经有了基础数据结构，可以来定义list对象的接口：

// functions for list library
static const luaL_Reg lib[] = {
    // list.new([cap]) -> ud 新建一个list并返回，可选的cap为预分配的容量
    {"new", list_new},
    // list.insert(ls, [pos,] value) 插入value。
    // 如果没有pos则插入到最后，否则插入到pos
    {"insert", list_insert},
    // list.remove(ls[, pos]) -> v 删除一个值，则返回这个值
    // 如果没有pos则删除最后的值，否则删除pos位置的值
    {"remove", list_remove},
    // list.totable(ls[, i [, j]]) -> table 将list保存转换为table返回
    // i, j为保存的范围，默认i=1, j=#ls
    {"totable", list_totable},
    // list.fromtable(ls, t, [, i [, j]]) 从table加载值到ls
    // i, j为加载的范围，默认i=1, j=#ls
    {"fromtable", list_fromtable},
    // list.extend(ls, ls2|t) 将ls2或t的值追加到ls尾
    // ls2为列表，t为table
    {"extend", list_extend},
    // list.indexof(ls, v) -> number|nil 返回v在ls中的索引，如果找不到返回nil
    {"indexof", list_indexof},
    // list.concat(ls [, sep [, i [, j]]]) -> string 将ls的内容串连成字符串返回
    // sep为分隔符，默认是空；i,j为范围，默认i=1, j=#ls
    {"concat", list_concat},
    // list.clear(ls[, shink]) 清空ls的内容，shink指定是否收缩内存
    {"clear", list_clear},
    // list.exchange(ls, idx1, idx2) 交换两个值的位置
    {"exchange", list_exchange},
    // list.sort(ls [, cmp [, key]]) 原地排序ls
    // cmp为比较函数，function(a, b) -> boolean，a < b 返回true
    // key函数返回元素的整型值用于排序，function(v) -> number
    // 如果key函数指定，则优先用key
    // 如果cmp函数指定，则用cmp
    // 否则用默认的a < b比较
    {"sort", list_sort},
    {NULL, NULL}
};

// functions for list metatable
static const luaL_Reg mlib[] = {
    // ls[i] = v 设值，v不能是nil
    // ls[#ls+1] = v 可增加项
    {"__newindex", list_newindex},
    // v = ls[i]，取值
    {"__index", list_index},
    // #ls 取长度
    {"__len", list_len},
    // gc时自动释放内容
    {"__gc", list_gc},
    // tostring(ls)
    {"__tostring", list_tostring},
    {NULL, NULL}
};

LUAMOD_API int luaopen_colua_list(lua_State *L) {
    luaL_checkversion(L);
    luaL_newmetatable(L, LIST_MT);      // 创建一个metatable用于list对象
    luaL_setfuncs(L, mlib, 0);
    luaL_newlib(L, lib);
    return 1;
}

从接口部分看，这个list提供了和table库很相似的函数，如list.insert, list.remove, list.concat, list.sort等，此外还参考了python的一些实用函数如list.extend, list.clear等。

这个list绝对不是一个玩具，它是一个各方面都均衡高效的列表，并且它解决了Table当列表的一些隐患，比如list不能将元素设置为nil，你只能插入或删除，由于Lua和其他语言的差异，需要nil的地方可用false代替。

按照前面一篇的测试用例，也给list写了下面的测试代码：

local function test_list1()
    local linsert = list.insert
    local ls = list.new()
    local c = 1000000
    local tm = os.clock()
    for i = 1, c do
        linsert(ls, i)
    end
    print("lua.list - insert after(1000000): ", os.clock() - tm)
end

local function test_list2()
    local linsert = list.insert
    local ls = list.new()
    local c = 100000
    local tm = os.clock()
    for i = 1, c do
        linsert(ls, 1, i)
    end
    print("lua.list - insert before(100000)", os.clock() - tm)
end

local function test_list3()
    local ls = list.new()
    local c = 1000000
    local linsert = list.insert
    local lremove = list.remove
    for i = 1, c do
        linsert(ls, i)
    end

    local tm = os.clock()
    for i = 1, c do
        lremove(ls)
    end
    print("lua.list - remove after(1000000)", os.clock() - tm)
end

local function test_list4()
    local ls = list.new()
    local c = 100000
    local linsert = list.insert
    local lremove = list.remove
    for i = 1, c do
        linsert(ls, i)
    end

    local tm = os.clock()
    for i = 1, c do
        lremove(ls, 1)
    end
    print("lua.list - remove before(100000)", os.clock() - tm)
end

测试结果如下：

lua.list - insert after(1000000):       0.09375
lua.list - insert before(100000)        0.859375
lua.list - remove after(1000000)        0.078125
lua.list - remove before(100000)        0.875

lua.table - insert after(1000000):      0.171875
lua.table - insert before(100000)       44.859375
lua.table - remove after(1000000)       0.203125
lua.table - remove before(100000)       44.421875

python-append(1000000)      0.0735228061676
python-insert(100000)       1.67143321037
python-pop-after(1000000)   0.0515899658203
python-pop-before(100000)   0.863451004028
  • insert after 比table快了将近1倍，仍然比python的慢一点点。
  • insert before 比table提高了几十倍，同时也比python快了一倍。
  • remove after 比table提高了2.5倍，仍然比python的慢一点点。
  • remove before 比table提高了几十倍，与python基本相同。

我们没有办法在各个方面超越python，但是却实实在在的比Table提高了很多。

下一篇将介绍这些接口函数的实现，下下一篇将介绍排序函数的实现，以及如何超越python的排序，敬请期待。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK