fuchencong

The way I am

0%

《lua 程序设计》读书笔记（7）：数据结构 & 数据文件和序列化

发表于 分类于

这篇文章将介绍 Lua 中的数据结构，其实 Lua 只提供了 表 这唯一的数据结构，但是通过 表 可以实现数组、字典等数据结构。之后将介绍如何在 Lua 中实现数据结构的序列化和反序列化。

数据结构

在 Lua 中可以通过表来实现其他语言提供的数据结构，例如数组、记录、列表、队列、集合等。

数组

在 Lua 中可以通过使用整数来索引表即可实现数组。因此数组的大小不用是固定的，而是可以按需增长。可以使用 0、1
或其他任何值作为数组的其实索引，但是 Lua 通常以 1 作为数组的起始索引。Lua 中的标准库和长度运算符都遵循这个惯例，如果数组索引不从 1 开始，这不能使用这些机制。可以通过表构造器在一句表达式中同时创建和初始化数组。

1
2
3
4
5
6
7
8
9
10
> a = {}
> for i = 1, 100 do
>> a[i] = 0
>> end
> print(#a)
100

> a = {1, 2, 3, 4, 5}
> print(#a)
5

矩阵和多维数组

在 Lua 中有两种方式表示矩阵：

  • 方式 1：使用一个不规则的数组，即数组的数组，也就是一个所有元素均是另一个表的表
  • 方式 2：将两个索引合并为 1 个，典型情况下，可以通过一个索引乘以一个合适的常量再加上第二个索引来实现这种效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
local mt = {}

N = 3
M = 2

for i = 1, N do
    local row = {}
    mt[i] = row
    for j = 1, M do
        row[j] = 0
    end
end


print(#mt)
print(#(mt[1]))
1
2
3
4
5
6
7
8
9
10
11
12
13
local mt = {}

N = 3
M = 2

for i = 1, N do
    local aux = (i - 1) * 2
    for j = 1, M do
        mt[aux + j] = 0
    end
end

print(#mt)

应用程序中会经常使用到稀疏矩阵（sparse matrix），这种矩阵中的大多数元素都是 0 或 nil。在 Lua 中使用表来实现的数组本身就是稀疏的。但是此时需要注意，由于有效元素之间存在空洞（nil），因此不能对稀疏矩阵使用长度运算符，相反，可以使用 pairs 来遍历非 nil 的元素：

1
2
3
4
5
6
7
8
9
10
11
> a[1] = 1
> a[3] = 3
> a[5]= 5
> #a
1
> for k, v in pairs(a) do
>> print(k, v)
>> end
1       1
3       3
5       5

链表

由于表是动态对象，所以可以在 Lua 中可以很容易实现链表。可以用表来表示每个节点，链接则为一个指向其他表引用的简单表字段。如下实现了一个单向链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
> l = nil
> l = {next = l, value = 1}
> l = {next = l, value = 2}
> l = {next = l, value = 3}
>
> n = l
> while n do
>> print(n.value)
>> n = n.next
>> end
3
2
1

双向链表或环形表等其他类型的链表也很容易实现。但是，由于 Lua 中通常无需链表即可以更简单的方式来表示数据，所以在 lua 中很少使用这些数据结构。

队列及双端队列

在 Lua 中实现队列的一种简单方法时是使用 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
33
34
35
36
37
38
39
function listNew()
    return {first = 0, last = -1}
end

function pushFirst(list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end

function pushLast(list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end

function 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 = list.first + 1
    return value
end

function 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

由于在 Lua 中可以使用表来表示数组，所以既可以在任意整数范围内索引数组。对于一个 64 位整型数，以每秒 1000 万次的速度进行插入也需要运行 3 万年才会发生溢出。

反向表

我们很少在 Lua 中进行搜索操作，相反使用被称为索引表或反向表的数据结构。如果想使用如下表来将一周中的某天名称转换为其在一周中的位置，一种方法是通过搜索这个表来寻找指定的名称，另外一种更高效的方式则是构造一个反向表：

1
> days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
1
2
3
4
5
> revDays = {["Sunday"] = 1, ["Monday"] = 2, ["Tuesday"] = 3, ["Wednesday"] = 4, ["Thursday"] = 5, ["Friday"] = 6, ["Saturday"] = 7}
> print(revDays["Monday"])
2
> print(revDays["Saturday"])
7

这个反向表可以不用手工声明，而是从原始的表中自动构造出反向表：

1
2
3
4
> revDays = {}
> for k, v in pairs(days) do
>> revDays[v] = k
>> end

集合与包

在 Lua 中可以以一种高效且简单的方式来表示集合，即将集合元素作为索引放入表中，那么对于指定的元素无需在搜索表，只需要使该元素检索表并检查结果是否为 nil 即可。

1
2
3
> reserved = {
>> ["white"] = true, ["if"] = true, ["else"] = true, ["do"] = true
>> }

可以借助一个辅助函数来构造集合，使得初始化过程更加清晰：

1
2
3
4
5
6
7
8
9
function Set(list)
    local set = {}
    for _, l in ipairs(list) do
        set[l] = true
    end
    return set
end

reserved = Set{"While", "end", "function", "local", }

包（bag）也被称为多重集合，与不同集合的不同之处在于其中的元素可以出现多次。Lua 中，包的简单表示类似于集合的表示，只不过其中每一个键都有一个对应的计数器。如果要插入一个元素，可以递增计数器：

1
2
3
> function insert(bag, element)
>> bag[element] = (bag[element] or 0) + 1
>> end

如果要删除一个元素，可以递减其计数器：

1
2
3
4
> function remove(tag, element)
>> local count = bag[element]
>> bag[element] = (count and coutn > 1) and count - 1 or nil
>> end

字符串缓冲区

在 Lua 中如下代码是不够高效的：

1
2
3
4
local buff = ""
for line in io.lines()do
    buf = buf .. line .. "\n"
end

因为 Lua 中字符串是不可变的，每次进行字符串连接时都需要重新生成的新的目标字符串并执行内存复制操作。为了解决该问题，我们可以把一个表当做字符串缓冲区，然后使用函数 table.concat 将指定列表中的所有字符串连接起来并返回连接后的结果：

1
2
3
4
5
6
local t = {}
for line in io.lines() do
    t[#t + 1] = line .. "\n"
end

local s = table.concat(t)

另外可以利用 table.concat 的第二个可选参数，用于指定插在字符串之间的分隔符。这样就不用在每行后插入换行符了：

1
2
3
4
5
6
local t = {}
for line in io.lines() do
    t[#t + 1] = line
end

local s = table.concat(t, "\n") .. "\n"

为了避免对最后一个换行符也使用连接符，一种方法是在字符串 t 后面添加一个空字符串：

1
2
t[#t + 1] = ""
s = table.concat(t, "\n")

图

Lua 允许开发人员使用多种实现表示图，每种实现都有其所适用的特定算法。如下展示了使用 Lua 来实现图算法中的路径查找功能：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
function name2node(graph, name)
    local node = graph[name]
    if not node then
        node = {name = name, adj = {}}
        graph[name] = node
    end
    return node
end

function readgraph()
    local graph = {}
    for line in io.lines() do
        local namefrom, nameto = string.match(line, "(%S+)%s+(%S+)")
        local from = name2node(graph, namefrom)
        local to = name2node(graph, nameto)
        from.adj[to] = true
    end
    return graph
end

function findpath(curr, to, path, visited)
    path = path or {}
    visited = visited or {}
    if visited[curr] then
        return nil
    end
    visited[curr] = true
    path[#path + 1] = curr
    if curr == to then
        return path
    end

    for node in pairs(curr.adj) do
        local p = findpath(node, to, path, visited)
        if p then return p end
    end

    table.remove(path)
end

function printgraph(path)
    for i = 1, #path do
        print(path[i].name)
    end
end


local g = readgraph()
local a = name2node(g, "a")
local b = name2node(g, "b")
local p = findpath(a, b)
if p then printgraph(p) end

数据文件和序列化

接下来将学习如何在 Lua 中写入序列化数据、读取序列化数据。

数据文件

对于文件格式来说，表构造器提供了一种有趣的替代方法。只需要在写入数据时，做一点额外的工作就能使得读取数据变得更加容易。该技巧就是将数据文件写成 Lua 代码，当代码运行时，程序也就把数据重建了。使用表构造器时，这些代码段看上去就会非常像是一个普通的数据文件。

所以如果处理的是出于自身需求而创建的数据文件，那么就可以将 Lua 的构造器用于格式定义。此时可以把每条数据记录表示为一个 Lua 构造器：

例如如下一个数据文件 data：

1
2
3
4
5
6
7
8
9
10
11
Entry {
    "Jack",
    15,
    "USA"
}

Entry {
    "Zhangsan",
    16,
    "China"
}

如下代码对该数据文件进行计数：

1
2
3
4
5
6
7
8
9
local count = 0

function Entry()
    count = count + 1
end

dofile("data")

print("number of entries: " .. count)

这段代码最核心的的两点：

  • Entry({code}) 等同于 Entry{code}，因为表是唯一的参数来调用函数 Entry()，因此可以省去 ()
  • dofile 用于执行指定文件中的代码

当文件不是太大时，可以使用键值对的表示方法，这种格式是所谓的自描述数据格式。此时字段的次序就不那么重要了。

序列化

我们经常需要将数据序列化/串行化，即将数据转换为字节流或字符流，以便将其存储到文件中或者通过网络传输。可以将序列化后的数据表示为 Lua 代码，当这些代码运行时，被序列化的数据就可以在读取程序中得到重建。

例如，如果想要恢复一个全局变量的值，那么可以使用形如 varname=exp 这样的代码，其中 varname 就是标识符，而 exp 则是创建这个值的代码。

  • 对于数值类型，用十进制保存浮点数可能会损失精度，可以使用十六进制格式来存储浮点型数以保留原始精度
  • 对于字符串类型，可以使用函数 string.format 的 %q 选项，该选项被设计为一种能够让 Lua 安全地反序列化字符串的方式来序列化字符串，它使用双引号括住字符串并且能正确地转义其中的双引号、换行符等。
  • Lua 5.3.3 对 %q 进行了扩展，使其也可以用于对数值、nil 和 Boolean 类型，进而能它们能够正确地被序列化和反序列化（该选项会以十六进制格式处理浮点类型以保存完整的精度）

如果要使用 [=[...]=] 来保存字符串，一定要选择恰当数量的等号，该数量要比原字符串中出现的最长等号序列长度大（例如大 1）。

1
2
3
4
5
6
7
8
9
10
11
12
function quote(s)
    local n = -1
    for w in string.gmatch(s, "]=*") do
        n = math.max(n, #w - 1)
    end

    local eq = string.rep("=", n + 1)
    return string.format(" [%s[\n%s]%s]", eq, s, eq)
end

print(quote("[[test]]"))
print(quote("[[test]===]"))

这段代码在生成目标字符串时，在长字符串的开头添加了一个换行符，是为了解决这样的问题：即原始字符串的开头如果包含换行符，在反序列化时这个换行符会被忽略，因此额外再添加一个换行符可以避免原始字符串中的换行符被忽略。

保存表有几种方法，如下是一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function serialize(o)
    local t = type(o)
    if t == "number" or t == "string" or t == "boolean" or t == "nil" then
        io.write(string.format("%q", o))
    elseif  t == "table" then
        io.write("{\n")
        for k, v in pairs(o) do
            io.write(" ", k, " = ")
            serialize(v)
            io.write("\n")
        end
        io.write("}\n")
    else
        error("can't serialize a " .. type(o))
    end
end

只要表结构是一棵树（即没有共享的子表和环），那么该函数甚至能处理嵌套的表。上面的代码假设表中的键都是合法的标识符，如果表的键是数字或者不是合法的 Lua 标识符，就会存在问题。可以以一种简单的方法解决该问题：

1
io.write(string.format(" [%s] = ", serialize(k)))

由于表构造器不能创建带循环或共享子表的表，所以如果要处理通用拓扑结构（例如带循环或共享子表） 的表，就需要采用不同的方法。我们需要引入名称来表示循环。

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
function basicSerialize(o)
    return string.format("%q", o)
end

function save(name, value, saved)
    saved = saved or {}
    io.write(name, "= ")
    if type(value) == "number" or type(value) == "string" then
        io.write(basicSerialize(value), "\n")
    elseif type(value) == "table" then
        if saved[value] then
            io.write(saved[value], "\n")
        else
            saved[value] = name
            io.write("{}\n")
            for k, v in pairs(value) do
                k = basicSerialize(k)
                local fname = string.format("%s[%s]", name, k)
                save(fname, v, saved)
            end
        end
    else
        error("cannot save a " .. type(value))
    end
end