Lua数据结构详解：表、数组与矩阵实现 | 南锋

南锋

南奔万里空，脱死锋镝余

Lua数据结构详解：表、数组与矩阵实现

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 8.4k 阅读时长 ≈ 8 分钟

Lua语言中的表并不是一种数据结构，它们是其他数据结构的基础。我们可以用Lua语言中的表来实现其他语言提供的数据结构，如数组、记录、列表、队列、集合等。而且，用Lua语言中的表实现这些数据结构还很高效。

在像C和Pascal这样更加传统的语言中，通常使用数组和列表来实现大多数数据结构。虽然在Lua语言中也可以使用表来实现数组和列表，但表实际上比数组和列表强大很多。使用表时，很多算法可以被简化。例如，由于表本身就支持任意数据类型的直接访问，因此我们很少在Lua语言中编写搜索算法。

数组

在Lua语言中，简单地使用整数来索引表即可实现数组。因此，数组的大小不用非得是固定的，而是可以按需增长的。通常，在初始化数组时就间接地定义了数组的大小。例如，在执行了以下的代码后，任何访问范围1~1000之外的元素都会返回nil而不是0：

1
2
3
4
local a = {}
for i = 1, 1000 do 
	a[i] = 0
end

长度运算符（#）正是基于此来计算数组大小的：

1
print(#a)

可以使用0、1或其他任何值来作为数组的起始索引：

1
2
3
4
a = {}
for i = -5 , 5 do
	a[i] = 0
end

不过，在Lua语言中一般以1作为数组的起始索引，Lua语言的标准库和长度运算符都遵循这个惯例。如果数组的索引不从1开始，那就不能使用这些机制。
可以通过表构造器在一句表达式中同时创建和初始化数组：

1
squares = {1,2,3,4,5,6,54,23,23,12}

这种表构造器根据需求要多大就能多大。在Lua语言中，利用数据描述文件创建包含几百万个元素组成的构造器很常见。

矩阵及多维数组

在Lua语言中，有两种方式来表示矩阵。第一种方式就是使用一个不规则数组，即数组的数组，也就是一个所有元素均是另一个表的表。例如，可以使用如下代码来创建一个全0元素的N*M维矩阵：

1
2
3
4
5
6
7
8
local mt = {}
for i = 1 , N do
	local row = {}
	mt[i] = row
	for j = 1, M do
		row[j] = 0
	end
end

由于表在Lua语言中是一种对象，因此在创建矩阵时必须显示地创建每一行。一方面，这比在C语言中直接声明一个多维数组更加具体；另一方面，这也给我们提供了很多的灵活性。例如，只需将前例中的内层循环改为for j = 1,i do … end就可以创建一个三角矩阵。使用这套代码，三角矩阵较原来的矩阵可以节约一半的内存。
在Lua中表示矩阵的第二种方式是将两个索引合并为一个。典型情况下，我们通过将第一个索引乘以一个合适的常量再加上第二个索引来实现这种效果。在这种方式下，我们可以使用以下的代码来创建一个全0元素的N*M维矩阵：

1
2
3
4
5
6
7
local mt = {}
for i = 1, N do
	local aux = (i -1) * M 
	for j = 1, M do
		mt[aux = j] = 0
	end
end

应用程序中经常会用到稀疏矩阵，这种矩阵中的大多数元素是0或nil。例如，我们可以使用邻接矩阵来表示图。当矩阵出元素的值为x时，表示图中的节点m和n是相连的，连接的权重为x；若上述的两个节点不相连，那么矩阵的 (m,n)处元素的值为nil。如果要表示一个具有1万个节点的图，那么需要一个包含1亿个元素的矩阵，但是其中大约只有5万个元素不为nil。许多有关数据结构的书籍都会深入地讨论如何实现这种稀疏矩阵而不必浪费800MB内存空间，但在Lua语言中却很少需要用到那些技巧。这是因为，我们使用表实现数组而表本来就是稀疏的。在第一种实现中，需要1万个表，每个表5个元素，总共5万个元素。在第二种实现中，只需要一个表，其中包含5万个元素。无论哪种实现，都是只非nil的元素才占用空间。
由于在有效元素之间存在空间，因此不能对稀疏举着使用长度运算符。这没什么大不了的，即使我们能够使用长度运算符，最好也不要那么做。对于大多数针对稀疏矩阵的操作来说，遍历空元素是非常低效的。相反，可以使用pairs来只遍历非nil的元素。例如，考虑如何进行由不规则数组表示的稀疏矩阵的矩阵乘法。
假设矩阵a[M,K]乘以矩阵b[K,N]的结果为矩阵c[M,N]，常见的矩阵相乘算法形如：

1
2
3
4
5
6
7
8
for i = 1, M do
	for j = 1, N do
		c[i][j] = 0
		for k = 1,K do
			c[i][j] = c[i][j] + a[i][k] * b[k][j]
		end
	end
end

外层的两个循环遍历了整个结果矩阵，然后使用内层循环计算每一个元素的值。
对于使用不规则矩阵实现的稀疏矩阵，内层循环会有问题。由于内层循环遍历的是一列b而不是一行，因此不能再此处使用pairs：这个循环必须遍历每一行来检查对应的行是否在对应列中有元素。除了遍历了少量非0元素以外，这个循环还遍历了所有的0元素。（由于不知道元素的空间位置，所以在其他场景下遍历一列可也能会有问题。）
以下的算法与之前的示例非常类似，但是该算法调换了两个内层循环的顺序。通过这个简单的调整，该算法避免了遍历列：

1
2
3
4
5
6
7
for i = 1, M do
	for k = 1 , K do
		for j = 1, N do
			c[i][j] = c[i][j] + a[i][k] * b [k][j]
		end
	end
end

这样，中间的一层循环遍历行a[i]，而内层循环遍历行b[k]。这两个遍历都可以使用pairs来实现遍历非0元素。由于一个空的稀疏矩阵本身就是使用0填充的，所以对结果矩阵c的初始化没有任何问题。
下面代码战士了上述算法的完整实现，其中使用了pairs来处理稀疏矩阵的元素。这种实现只访问非nil元素，同时结果也是稀疏矩阵。此外，下面的代码还删去了结果中偶然为0的元素。

稀疏矩阵相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function mult(a,b)
	local c = {}
	for i = 1, #a do
		local resultline = {}
		for k ,va in pairs(a[i]) do
			for j , vb in pairs(b[k]) do
				local res = (resultline[j] or 0 ) + va * vb
				resultline[j] = (res ~= 0) and res  or nil
			end
		end
		c[i] = resultline
	end
	return c
end

链表

由于表是动态对象，所以在Lua语言中可以很容易地实现链表。我们可以把每个节点用一个表来表示，链接则为一个包含指向其他表的引用的简单表字段。例如，让我们实现一个单链表，其中每个节点具有两个字段value和next。最简单的变量就是根节点：

1
list = nil

要在表头插入一个值为v的元素，可以使用如下代码：

1
list = {next = list, value = v}

可以通过如下的方式遍历链表：

1
2
3
4
5
local l = list
while l do
	visit l.value
	l = l.next
end

诸如双向链表或环形表等其他类型的链表也很容易实现。不过，由于通常无须链表即可用更简单的方式来表示数据，所以在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
function listNew()
	return {first = 0 ,last = 1}
end

function pushFisrt(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 = 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

如果希望严格地遵循队列的规范使用这个结构，那么就只能调用pushLast和popFirst函数，first和last都会不断增长。不过，由于我们在Lua语言中使用表来表示数组，所以我们既可以在1-20的范围内对数组进行索引，也可以在16777201-16777220的范围内索引数组。对于一个64为整型数而言，以每秒1000万次的速度进行插入也需要运行3万年才会发生溢出的问题。

反向表

我们很少在Lua语言中进行索引操作。但是，我们使用被称为索引表或反向表的数据结构。
假设有一个存放了一周每一天名称的表：

1
days = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"}

如果想要将一周每一天的名称转换为其在一周里的位置，那么可以通过索引这表来寻找指定的名称。不过，一种更高效的方式是构造一个方向表，假定为revDays，该表中的索引为一周每一天的名称而值为其在一周里的位置。这个表形如：

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

然后，只需要直接在反向表中根据名称进行索引就可以了：

1
2
x = "Tuesday"
print(revDays[x])				-- 3

当然，这个反向表不同手工声明，可以从原始的表中自动地构造出方向标：

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

上例中的循环会对每个元素days进行赋值，变量k获取到的是键(1,2,…)而变量v获取到的是值(“Sunday”,”Monday”,…)。

集合与包

假设我们想列出一个程序源代码中的所有标识符，同时过滤掉其中的保留字。一些C程序员可能倾向于使用字符串数组来表示保留字集合，然后搜索这个数组来决定某个单词是否属于该集合。为了提高搜索的速度，他们还可能使用二叉树来表示该集合。
在Lua语言中，还可以用一中高效且简单的方式来表示这类集合，即集合元素作为索引放入表中。那么，对于指定的元素无须再搜索表，只需要该元素检索表并检查结果是否为nil即可。以上述需求为例，代码形如：

1
2
3
4
5
6
reserved = {["while"] = true, ["if"] = true,["else"] = true,["do"] =true,}
	for w in string.gmatch(s,"[%a_][%w_]*") do
		if not reserved[w] then
			do something with 'w'
		end
	end

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

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",}

我们还可以使用另一个集合来保存标识符：

1
2
3
4
5
6
7
8
9
10
local ids = {}
for w in string.gmatch(s,"[%a_][%w_]*") do
	if not reserved[w] then
		ids[w] = true
	end
end
-- 输出每一个标识符
for w in pairs(ids) do 
	print(w)
end

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

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

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

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

只有当计数器存在且大于0时我们才会保留计数器。

字符串缓冲区

假设我们正在开发一段处理字符串的程序，比如逐行地读取一个文件。典型的代码可能形如：

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

虽然这段Lua语言代码看似能够正常工作，但实际上在处理大文件时却可能导致巨大的性能开销。
这是为什么呢？为了搞清楚到底发生了什么，让我们想象一下读取循环中发生了什么。假设每行有20字节，当我们读取了大概2500行后，buff就会变成一个50KB大小的字符串。在Lua语言中进行字符串连接buff..line.."\n"时，会创建一个50020字节的新字符串，然后从buff中复制50000字节中到这个新字符串中。这样，对于后续的每一行，Lua语言都需要移动大概50KB且还在不断增长的内存。因此，该算法的时间复杂度是二次方的。在读取了100行以后，Lua语言就已经移动了至少5MB内存。当Lua语言完成了350KB的读取后，它已经至少移动了50GB的数据。
对于较小的字符串，上述循环并没什么问题。当读取整个文件时，Lua语言提供了带有参数的函数io.read(“a”)来一次性读取整个文件。不过，有时候我们必须面对这个问题。Java提供了StringBuffer类还解决这个问题；而在Lua语言中，我们可以把一个表当做字符串缓冲区，其关键是使用函数table.concat，这个函数会将指定列表中的所有字符串连接起来并返回连接后的结果。使用函数concat可以这样重写上述循环：

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

之前的代码读取同样的文件需要超过半分钟，而上述实现则只需要不到0.05秒。我们还可以做得更好。函数concat还有第2个可选参数，用于指定插在字符串间的分隔符。有了这个分隔符，我们就不必在每行后插入换行符了。

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

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

虽然函数concat能够在字符串之间插入分隔符，但我们还需要增阿基最后一个换行符。最后一次字符串连接创建了结果字符串的一个副本，这个副本可能已经相当长了。虽然没有直接的选项能够让函数concat插入这个额外的分隔符，但我们可以想办法绕过，只需在字符串t后面添加一个空字符串就行了：

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

现在，正如我们所期望的那样，函数concat会在结果字符串的额最后添加一个换行符。

图形

像其他现代编程语言一眼个，Lua语言也允许开发人员使用多种实现表示图，每种实现都有其所使用的特定算法。
我们使用一个由两个字段组成的表来表示每个节点，即name(节点名称)和adj(与此节点邻接的节点和集合)。由于我们会从一个文本文件中加载图对应的数据，所以需要能够根据节点的名称来寻找指定节点的方法。因此，我们使用了一个额外的表来建立节点和节点名称之间的映射。函数name2node可以根据指定节点的名称返回对应的节点：

1
2
3
4
5
6
7
8
local function name2node(graph,name)
	local node = graph[name]
	if not node then
		node = {name = name ,adj = {}}
		graph[name] = node 
	end
	return node 
end

示例：从文件中加载图

1
2
3
4
5
6
7
8
9
10
11
12
13
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)
		-- 把‘to’增加到邻接集合'from'中
		from.adj[to] = true
	end
	return graph
end

该函数逐行地读取一个文件，文件的每一行中有两个节点的名称，表示从第1个节点到第2个节点有一条边。对于每一行，调用函数string.match将一行中的两个节点的名称分开，然后根据名称找到对应的节点，最后将这些节点连接在一起。

示例：寻找两个节点之间的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

函数findpath使用深度优先遍历搜索两个节点之间的路径。该函数的第1个参数是当前节点，第2个参数是目标节点，第3个参数用于保存从起点到当前节点的路径，最后一个参数为所有已被访问节点的几何。
为了测试上述代码，我们编写一个打印一条路径的函数，再编写一些代码让上述所有代码跑起来：

1
2
3
4
5
6
7
8
9
10
11
function printpath(path)
	for i = 1, #path do 
		print(path[i].name)
	end
end

g = readgraph()
a = name2node(g,"a")
b = name2node(g,"b")
p = findpath(a,b)
if p then printpath(p) end
+