Lua 第14部分 数据结构

14.1  数组

        Lua 语言中的表并不是一种数据结构，它们是其他数据结构的基础。我们可以用 Lua 语言中的表来实现其他语言提供的数据结构，如数组、记录、列表、队列、集合等。而且，用Lua 语言中的表实现这些数据结构还很高效。
        在像 C 和 Pascal 这样更加传统的语言中，通常使用数组和列表（列表＝记录＋指针）来实现大多数数据结构。虽然在 Lua 语言中也可以使用表来实现数组和列表，但表实际上比数组和列表强大得多。使用表时，很多算法可以被简化。例如，由于表本身就支持任意数据类型的直接访问，因此我们很少在 Lua 语言中编写搜索算法。
        学习如何高效地使用表需要花费一点时间。这里，我们先来学习如何通过表来实现一些典型的数据结构并给出一些使用这些数据结构的例子。首先，我们学习数组和列表，这并不是因为需要它们作为其他结构的基础，而是因为大多数程序员已经对数组和列表比较熟悉了。

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

local a = {}		-- 新数组
for i = 1, 1000 doa[i] = 0
end

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

print(#a)
> 1000

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

-- 创建一个索引范围为-5~5的数组
a = {}
for i = -5, 5 doa[i] = 0
end

        不过，在 Lua 语言中一般以 1 作为数组的起始索引，Lua 语言的标准库和长度运算符都遵循这个惯例。 如果数组的索引不从 1 开始，那就不能使用这些机制 。

        可以通过表构造器在一句表达式中同时创建和初始化数组：

squares = {1, 4, 9, 16, 25, 36, 49, 64, 81}

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

14.2  矩阵及多维数组

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

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

由于表在 Lua 语言中是一种对象，因此在创建矩阵时必须显式地创建每一行。一方面，这比在 C 语言中直接声明一个多维数组更加具体；另 一方面，这也给我们提供了更多的灵活性。例如，只需将前例中的内层循环改为 for j=1, i do ... end 就可以创建一个三角形矩阵。使用这套代码，三角形矩阵较原来的矩阵可以节约一半的内存。

        在 Lua 中表示矩阵的第二种方式是将两个索引合并为一个。典型情况下，我们通过将第一个索引乘以一个合适的常量再加上第二个索引来实现这种效果。在这种方式下，我们可以使用以下的代码来创建一个全 0 元素的 N×M 维矩阵：

local mt = {}
for i = 1, N dolocal aux = (i - 1) * Mfor j = 1, M domt[aux + j] = 0end
end

        应用程序中经常会用到稀疏矩阵，这种矩阵中的大多数元素是 0 或 nil。例如，我们可以使用邻接矩阵来表示图。当矩阵（ m, n ）处元素的值为x时，表示图中的节点 m 和 n 是相连的，连接的权重为 x ；若上述的两个节点不相连，那么矩阵的（ m,n）处元素的值为 nil。如果要表示一个具有 1 万个节点的图（其中每个节点有 5 个邻居），那么需要一个能包含 1 亿个元素的矩阵（ 10000 列×10000 行的方阵），但是其中大约只有 5 万个元素不为nil（每行有 5 列不为 nil ，对应每个节点有 5 个邻居）。许多有关数据结构的书籍都会深入地讨论如何实现这种稀疏矩阵而不必浪费 800MB 内存空间，但在 Lua 语言中却很少需要用到那些技巧。这是因为，我们使用表实现数组而表本来就是稀疏的。在第一种实现中（表的表），需要 1 万个表，每个表包含 5 个元素，总共 5 万个元素。在第二种实现中，只需要一个表，其中包含 5 万个元素。无论哪种实现，都只有非 nil 的元素才占用空间。

        由于在有效元素之间存在空洞（ nil 值），因此不能对稀疏矩阵使用长度运算符。这没什么大不了的，即使我们能够使用长度运算符，最好也不要那么做。对于大多数针对稀疏矩阵的操作来说，遍历空元素是非常低效的。相反，可以使用 pairs 来只遍历非 nil 的元素。例如，考虑如何进行由不规则数组表示的稀疏矩阵的矩阵乘法。

        假设矩阵 a[M,K］乘以矩阵 b[K,N］的结果为矩阵 c[ M, N]，常见的矩阵相乘算法形如 ：

for i = 1, M dofor j = 1, N doc[i][j] = 0for k = 1, K doc[i][j] = c[i][j] + a[i][k] * b[k][j]endend
end

外层的两个循环遍历了整个结果矩阵，然后使用内层循环计算每一个元素的值。

        对于使用不规则矩阵实现的稀疏矩阵，内层循环会有问题。由于内层循环遍历的是一列b而不是一行，因此不能在此处使用 pairs ：这个循环必须遍历每一行来检查对应的行是否在对应列中有元素。除了遍历了少量非 0 元素以外，这个循环还遍历了所有的 0 元素。（由于不知道元素的空间位置，所以在其他场景下遍历一列也可能会有问题。）

        以下的算法与之前的示例非常类似，但是该算法调换了两个内层循环的顺序。通过这个简单的调整，该算法避免了遍历列 ：

for i = 1, M dofor k = 1, K dofor j = 1, N doc[i][j] = c[i][j] + a[i][k] * b[k][j]endend
end

这样，中间的一层循环遍历行 a[i] ，而内层循环遍历行 b[k] 。这两个遍历都可以使用 pairs来实现仅遍历非 0 元素。由于一个空的稀疏矩阵本身就是使用 0 填充的，所以对结果矩阵 c 的初始化没有任何问题。

        示例14.1展示了上述算法的完整实现，其中使用了 pairs 来处理稀疏的元素。这种实现只访问非 nil 元素，同时结果也是稀疏矩阵。此外，下面的代码还删去了结果中偶然为 0 的元素 。

示例 14.1 稀疏矩阵相乘：

function mult (a, b)local c = {}			-- 结果矩阵for i = 1, #a dolocal resultlint = {}			-- 即'c[i]'for k, va in pairs(a[i]) do			-- 'va'即a[i][k]for j, vb in pairs(b[k]) do			-- 'vb'即b[k][j]local res = (resultlint[j] or 0) + va * vbresultlint[j] = (res ~= 0) and res or nilendendc[i] = resultlintendreturn c
end

14.3  链表

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

list = nil

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

list = {next = list, value = v}

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

local l = list
while l dovisit l.valuel = l.next
end

        诸如双向链表或环形表等其他类型的链表也很容易实现。不过，由于通常无须链表即可用更简单的方式来表示数据，所以在 Lua 语言中很少需要用到这些数据结构。例如，我们可以通过一个无界数组来表示栈。

14.4  队列及双端队列

        在 Lua 语言中实现队列的一种简单方法是使用 table 标准库中的函数 insert和 remove 。这两个函数可以在一个数组的任意位置插入或删除元素，同时根据所做的操作移动其他元素。不过，这种移动对于较大的结构来说开销很大。一种更高效的实现是使用两个索引，一个指向第一个元素，另一个指向最后一个元素。使用这种实现方式，我们就可以像在示例 14.2 中所展示的那样以 O(1)时间复杂度同时在首尾两端插入或删除元素了 。

示例 14.2 一个双端队列

function listNew ()return {first = 0, last = -1}
endfunction pushFirst (list, value)local first = list.first - 1list.first = firstlist[first] = value
endfunction pushLast (list, value)local last = list.last + 1list.last = lastlist[last] = value
endfunction popFirst (list)local first = list.firstif first > list.last then error("list is empty") endlocal value = list[first]list[first] = nil					-- 使得元素能够被垃圾回收list.first = first + 1return value
endfunction popLast (list)local last = list.lastif list.first > last then error("list is empty") endlocal value = list[last]list[last] = nil					-- 使得元素能够被垃圾回收list.last = last - 1return value
end

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

14.5  反向表

        正如此前提到的，我们很少在 Lua 语言中进行搜索操作。相反，我们使用被称为索引表或反向表的数据结构。

        假设有一个存放了一周每一天名称的表：

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

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

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

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

x = "Tuesday"
print(revDays[x])
> 3

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

revDays = {}
for k,v in pairs(days) dorevDays[v] = k
end

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

14.6  集合与包

        假设我们想列出一个程序源代码中的所有标识符，同时过滤掉其中的保留字。一些 C 程序员可能倾向于使用字符串数组来表示保留字集合，然后搜索这个数组来决定某个单词是否属于该集合。为了提高搜索的速度，他们还可能会使用二叉树来表示该集合。

        在 Lua 语言中，还可以用一种高效且简单的方式来表示这类集合，即将集合元素作为索引放入表中。那么，对于指定的元素无须再搜索表，只需用该元素检索表并检查结果是否为nil即可。以上述需求为例，代码形如：

reserved = {["while"] = true, ["if"] = true,["else"] = true, ["do"] = true,
}for w in string.gmatch(s, "[%a_][%w_]*") doif not reserved[w] thendo something with 'w'		-- 'w'不是一个保留字end
end

（在定义 reserved 时，由于 while 是 Lua 语言的保留字，所以不能直接写成 while=true，而应该写为 ［" while"］＝ true 。 ）

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

function Set (list)local set = {}for _, l in ipairs(list) do set[l] = true endreturn set 
endreserved = Set{"while", "end", "function", "local",}

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

local ids = {}
for w in string.gmatch(s, "[%a_][%w_]*") doif not reserved[w] thenids[w] = trueend
end-- 输出每一个标识符
for w in pairs(ids) do print(w) end

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

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

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

14.7  字符串缓冲区

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

local buff = ""
for line in io.lines() dobuff = buff .. line .. "\n"
end

虽然这段 Lua 语言代码看似能够正常工作，但实际上在处理大文件时却可能导致巨大的性能开销 。例如，在笔者的新机器上用这段代码读取一个 4.5MB 大小的文件需要超过 30 秒的时间 。

        这是为什么呢？为了搞清楚到底发生了什么，让我们想象一下读取循环中发生了什么。假设每行有 20 字节，当我们读取了大概 2500 行后，buff 就会变成一个 50KB 大小的字符串。在 Lua 语言中进行字符串连接 buff ..  line  .."\n" 时，会创建一个 50020 字节的新字符串，然后从 buff 中复制 50000 字节中到这个新字符串中。这样，对于后续的每一行，Lua 语言都需要移动大概 50KB 且还在不断增长的内存。因此，该算法的时间复杂度是二次方的。在读取了 100 行（仅 2KB ）以后，Lua 语言就已经移动了至少 5MB 内存。当 Lua 语言完成了 350KB 的读取后，它已经至少移动了 50 GB 的数据。（这个问题不是 Lua 语言特有的：在其他语言中，只要字符串是不可变值，就会出现类似的问题，其中最有名的例子就是 Java 。 ）

       在继续学习之前，我们必须说明，上述场景中的情况并不常见。对于较小的字符串，上述循环并没什么问题。 当读取整个文件时， Lua 语言提供了带有参数的函数 io.read("a") 来一次性地读取整个文件。不过，有时候我们必须面对这个问题。Java 提供了 StringBuffer类来解决这个问题；而在 Lua 语言中，我们可以把一个表当作字符串缓冲区，其关键是使用函数 table.concat，这个函数会将指定列表中的所有字符串连接起来并返回连接后的结果。使用函数 concat 可以这样重写上述循环 ：

local t = {}
for line in io.lines() dot[#t + 1] = line
end
s = table.concat( t, "\n") .. "\n"

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

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

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

14.8 图形

      像其他现代编程语言一样， Lua 语言也允许开发人员使用多种实现表示图，每种实现都有其所适用的特定算法。这里，我们接下来将介绍一种简单的面向对象的实现方式，在这种实现中使用对象来表示节点（实际上是表）、将边（arc ）表示为节点之间的引用。

      我们使用一个由两个字段组成的表来表示每个节点，即 name（节点的名称）和 adj（与此节点邻接的节点的集合）。由于我们会从一个文本文件中加载图对应的数据，所以需要能够根据节点的名称来寻找指定节点的方法。因此，我们使用了一个额外的表来建立节点和节点名称之间的映射。函数 name2node 可以根据指定节点的名称返回对应的节点：

local function name2node (graph, name)local node = graph[name]if not node then-- 节点不存在，创建一个新节点node = {name = name, adj = {}}gra[name] = nodeendreturn node
end

示例 14.3 展示了构造图的函数。

function readgrap ()local graph = {}for line in io.lines() do-- 把一行分隔为两个名字local namefrom, nameto = string.match(line, "(%S+)%s+(%S+)")-- 找到对应的节点local from = name2node(grap, namefrom)local to = name2node(grap, nameto)-- 把'to'增加到邻接集合'from'中from.adj[to] = trueendreturn graph
end

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

示例 14.4展示了一个使用这种图的算法。

function findpath (curr, to, path, visited)path = path or {}visited = visited or {}if visited[curr] then		-- 是否节点已被访问？return nil				-- 不存在路径endvisited[curr] = true		-- 标记节点为已被访问path[#path + 1] = curr		-- 增加到路径中if curr == to then			-- 是否是最后一个节点？return path end-- 尝试所有的邻接节点for node in pairs(curr.adj) dolocal p = findpath(node, to, path, visited)if p then return p endendtable.remove(path)			-- 从路径中删除节点
end

      函数 findpath 使用深度优先遍历搜索两个节点之间的路径。该函数的第 1 个参数是当前节点，第 2 个参数是目标节点，第 3 个参数用于保存从起点到当前节点的路径，最后一个参数为所有已被访问节点的集合（用于避免回路）。 请读者注意分析该算法是如何不通过节点名称而直接对节点进行操作的。例如，visited 是一个节点的集合，而不是节点名称的集合。类似地，path 也是一个节点的列表。

        为了测试上述代码，我们编写一个打印一条路径的函数，再编写一些代码让上述所有代码跑起来：

function printpath (path)for i = 1, #path doprint(path[i].name)end
endg = readgrap()
a = name2node(g, "a")
b = name2node(g, "b")
p = findpath(a, b)
if p then printpath(p) end