《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