Lua数据结构的实现

topic
1.7k 词

《Lua程序设计》笔记：高效地使用table来实现一些传统的数据结构

1 数组

Lua库和长度操作符都遵循索引从1开始的约定。

2 多维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

mt = {}
for i=1, N do
    mt[i] = {}
    for j=1, M do
        mt[i][j] = 0
    end
end
--合并索引（i*常量 + j）
mt = {}
for i=1, N do
    for j=1, M do
        mt[(i-1)*M+j] = 0
    end
end

3 链表、队列

table是动态实体，所以实现链表很方便；实现队列的话，使用table库的insert、remove。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
--主要是new/pushlast/popfirst
List = {}
function ()
    return {first=0, last=-1}
end
function List.pushfirst(list, value)
    local first = list.first-1
    list.first = first
    list[first] = value
end
function List.pushlast(list, value)
    local last = list.last+1
    list.last = last
    list[last] = value
end
function List.popfirst(list)
    local first = list.first
    if first>list.last then error('list is empty') end
    local value = list[first]
    --允许垃圾收集
    list[first] = nil
    list.first = first+1
    return value
end
function List.poplast(list)
    local last = list.last
    if list.first>last then error('list is empty') end
    local value = list[last]
    list[last] = nil
    list.last = last-1
    return value
end

4 集合、包

将集合元素作为索引放入table中；则对任意值都无需搜索table，直接索引即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Set(list)
    local set = {}
    for _, l in ipairs(list) do set[l] = true end
    return set
end

function Bag(list)
    local bag = {}
    for _, l in ipairs(list) do bag[l] = 1 end
    return bag
end
function insert(bag, element)
    bag[element] = (bag[element] or 0)+1
end
function remove(bag, element)
    local count = bag[element]
    --递减其计数器
    bag[element] = (count and count>1) and (count-1) or nil
end

5 字符串缓冲

只要字符串是immutable值，不断的连接就会造成性能浪费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
--读文件的正确姿势
local t = {}
for line in io.lines do
    t[#t+1] = line
end
--欺骗concat，在结尾处添加换行
t[#t+1] = ''
local s = table.concat(t, 'n')

--“汉诺塔”实现
function addString(stack, s)
    stack[#stack+1] = s
    for i = #stack-1, 1, -1 do
        if #stack[i] > #stack[i+1] then
            break
        end
        --如果新字符串更大，则连接、压缩栈
        stack[i] = stack[i] .. stack[i+1]
        stack[i+1] = nil
    end
end