Lua 数据结构

一、Lua 中的数据结构

Lua 中并没有像 java、kotlin 语言有专门的数组、列表、集合等数据结构的类，而只提供 table 类型，但他很强大而且也很灵活，而且也在很多场景中天然的就解决了如何对接和使用的问题（例如模块的引入，这在后面的文章会进行分享）

话说回来，Lua 没有提供专门的类进行支持，所以我们接下来就分享如何用 table 来表示各种数据结构。

Lua 中只要使用整数来作为 table 的索引，就可以达到数组的效果。但有些不同的是， 因为 table 的长度是不固定的，所以 Lua 数组的长度并不像 java、kotlin 那样是固定长度的。

2-1、初始化一个数组

我们可以使用循环创建一个数组，在被初始化的值被获取时则是有值的，未被初始化则为 nil。

local array = {}
for i = 1, 100 do
    array[i] = 0
print("#array", #array)             --> #array	100
print("array[9]", array[9])         --> array[9]	0
print("array[101]", array[101])     --> array[101]	nil
2-2、修改初始化起始下标
可以进行修改起始下标，只是这个会有一个问题，长度的计算会不准确，因为 Lua 的索引一般都是从 1 开始，从下面的例子体会一下
local array = {}
for i = -5, 5 do
    array[i] = 0
-- 这里的长度为 5 是因为从 1 开始计算
print("#array", #array)             --> #array	5
print("array[-2]", array[-2])       --> array[-2]	0
print("array[5]", array[5])         --> array[5]	0
2-3、创建且初始化数组
还有一种简单的创建方式，在创建时初始化数组




    

这是 table 的一种创建方式，可以查看之前分享的文章《Lua 数据类型——表》
local array = { 1, 3, 5, 7, 9 }
print("#array", #array)             --> #array	5
print("array[3]", array[3])         --> array[3]	5
print("array[12]", array[12])       --> array[12]	nil
3-1、矩阵存储
Lua 的矩阵并没有规定存在的形式是怎样的，所以我们可以通过两种方式来存储。
3-1-1、多维数组
多维数组在 java、kotlin 中最为常见，就是一个表中的所有元素又是一个表，如此循环，达到多维效果。
因为比较常规我们就直接上代码，看看 Lua 是如何用二维表现矩阵
local M = 5
local N = 5
local matrix = {}
-- 初始化数组
for i = 1, M do
    local row = {}
    matrix[i] = row
    for j = 1, N do
        row[j] = j + i
-- 打印数组
for i = 1, #matrix do
    local row = matrix[i]
    local rowContent = ""
    for j = 1, #row do
        rowContent = rowContent .. " " .. row[j]
    print(rowContent)
--> 2 3 4 5 6
--> 3 4 5 6 7
--> 4 5 6 7 8
--> 5 6 7 8 9
--> 6 7 8 9 10
3-1-2、一维数组
用一维数组表示多维数组（矩阵的话是二维），实质上只要控制要每一行的跨度（即每一行的元素个数），自己管理好元素的下标，保证元素间不相互覆盖，而且能在需要的时候取出元素。
local matrix = {}
local M = 5
local N = 5
for i = 1, N do
    local aux = (i - 1) * M
    for j = 1, M do
        matrix[aux + j] = j + i
local content = ""
for i, v in ipairs(matrix) do
    content = content .. " " .. v
    if i % 5 == 0 then
        content = content .. "\n"
print(content)
--> 2 3 4 5 6
--> 3 4 5 6 7
--> 4 5 6 7 8
--> 5 6 7 8 9
--> 6 7 8 9 10
3-2、矩阵相乘
3-2-1、常规矩阵相乘
对于矩阵相乘，我们最先想到的肯定是 “行乘列”，正如如下代码
local a = {
    { 1, nil },
    { nil, 4 },
    { 3, 5 }
local b = {
    { 1, 3, nil, 5 },
    { 2, nil, 6, 4 }
local M = 3
local N = 4
local K = 2
local c = {}
-- 初始化 c 矩阵
for i = 1, M do
    local row = {}
    c[i] = row
    for j = 1, N do
        row[j] = 0
-- 遍历每一个元素，行乘列的形式处理
-- c = a x b
for i = 1, M do
    for j = 1, N do
        for k = 1, K do
            c[i][j] = c[i][j] + (a[i][k] or 0) * (b[k][j] or 0)
-- 打印每个元素
for i = 1, #c do
    local row = c[i]
    local rowContent = ""
    for j = 1, #row do
        rowContent = rowContent .. " " .. row[j]
    print(rowContent)
--> 1 3 0 5
--> 8 0 24 16
--> 13 9 30 35
3-2-3、稀疏矩阵相乘
这种处理方式对于常规的矩阵没有问题，但是对于稀疏矩阵就会有不必要的性能开销和空间的浪费。
所以我们可以换一种思路，在之前的文章中，有使用过 pairs 进行遍历 table ，该函数的特点是保证遍历 table 中的所有元素，但不保证先后顺序。
那问题又来了，我们在上面的遍历中，行乘列的话，B 矩阵遍历的是列而不是行，所以可以调整一下刚才的循环方式，把内循环顺序换一下即可达到行乘行
可以借助上面这张图理解
上一小节的处理方式：取 A 矩阵和 B 矩阵各自的蓝色小点和粉色小点相乘然后相加，循环直至的处所有结果
本小节的处理方式：取 A 矩阵的蓝色小点和 B 矩阵的蓝色小点相乘，结果存入 C 中的对应位置，然后在取 A 矩阵的粉色小点和 B 矩阵的粉色小点相乘，结果和 C 的结果相加，从而达到行乘行
local a = {
    { 1, nil },
    { nil, 4 },
    { 3, 5 }
local b = {
    { 1, 3, nil, 5 },
    { 2, nil, 6, 4 }
local M = 3
local N = 4
local K = 2
local c = {}
-- 初始化 c 矩阵
for i = 1, M do
    local row = {}
    c[i] = row
    for j = 1, N do
        row[j] = 0
-- 遍历每一个元素，行乘列的形式处理
-- c = a x b
for i = 1, M do
    for k = 1, K do
        for j = 1, N do
            c[i][j] = c[i][j] + (a[i][k] or 0) * (b[k][j] or 0)
-- 打印每个元素
for i = 1, #c do
    local row = c[i]
    local rowContent = ""
    for j = 1, #row do
        rowContent = rowContent .. " " .. row[j]
    print(rowContent)
--> 1 3 0 5
--> 8 0 24 16
--> 13 9 30 35
聪明的你肯定会发现，现在的操作 paris 还没用上，所以接下来就要进行再一次调整，得到最终的效果
下面代码需要注意几个小点：
使用 pairs 遍历元素，避免不必要的遍历
最终结果检测是否为 0 ，如果为 0 则置为 nil ，避免不必要的开销
local a = {
    { 1, nil },
    { nil, 4 },
    { 3, 5 }
local b = {
    { 1, 3, nil, 5 },
    { 2, nil, 6, 4 }
--- a 和 b 是矩阵
local function mulMatrix(matrixA, matrixB)
    local c = {}
    -- 遍历 a 所有行
    for i = 1, #matrixA do
        -- c 矩阵的行结果
        local resultLine = {}
        -- 遍历 a 矩阵行的每个内容，所有的 nil 都会被跳过
        for k, va in pairs(matrixA[i]) do
            -- 遍历 b 矩阵行的每个内容，所有 nil 都会被跳过
            for j, vb in pairs(matrixB[k]) do
                local res = (resultLine[j] or 0) + va * vb
                resultLine[j] = (res ~= 0) and res or nil
        c[i] = resultLine
    return c
local c = mulMatrix(a, b)
-- 打印每个元素
for i = 1, #c do
    local row = c[i]
    local rowContent = ""
    for j = 1, #row do
        rowContent = rowContent .. " " .. (row[j] or "nil")
    print(rowContent)
--> 1 3 nil 5
--> 8 nil 24 16
--> 13 9 30 35
Lua 中的链表是由一个个的 table 组成，每个 table 中有一个字段是指向下一个 table 。
根据上面图，我们可以编写出如下构建一个链表
local aPoint = {value = "A", next = nil}
local bPoint = {value = "B", next = aPoint}
local cPoint = {value = "C", next = bPoint}
进行遍历也是很方便，在 Lua 中 nil 就是 false ，所以使用循环遍历一下就可以了
local list = cPoint
while list do
    print(list.value)
    list = list.next
同样队列还是使用 table 来实现，因为 Lua 中的 table 并没有长度的约束，所以只要控制好单端的出入（即普通队列）或是双端的出入（双端队列）即可。
直接上代码，我们使用 table 的 insert 和 remove 便能达到双端队列的效果（普通队列的话，只需要控制在末尾端的出入便可）
local queue = {}
print("---------------------")
print("前面插入：")
table.insert(queue, 1, -10)
table.insert(queue, 1, -5)
table.insert(queue, 1, -1)
---------------------------------------
--- 此时队列内容 -1，-5，-10
---------------------------------------
print(table.remove(queue, 1))       --> -1
print(table.remove(queue, 1))       --> -5
print("---------------------")
print("后面插入：")
table.insert(queue, #queue + 1, 10)
table.insert(queue, #queue + 1, 5)
table.insert(queue, #queue + 1, 1)
---------------------------------------
--- 此时队列内容 -10，10，5，1
---------------------------------------
print(table.remove(queue, #queue))  --> 1
print(table.remove(queue, #queue))  --> 5
print("---------------------")
print("输出全部：")
---------------------------------------
--- 此时队列内容 -10，10
---------------------------------------
for k, v in pairs(queue) do
    print(k .. "-->" .. v)
--> 1-->-10
--> 2-->10
但是这里有一个问题，我们在 "Lua-表" 的一章分享中，提及 table 的 insert 和 remove 如果插入点不在末尾则会导致后面的元素移动，在较小数据的情况下，这一性能损耗可以忽略，但在大量数据的情况下，则是一个性能点。
所以我们可以用两个字段来维护队列的头尾，这样就不用挪动元素
function listNew()
    return { first = 0, last = -1 }
function pushFirst(list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
function pushLast(list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
function popFirst(list)
    local first = list.first
    if first > list.last then
        error("list is empty")
    local value = list[first]
    list[first] = nil
    list.first = first + 1
    return value
function popLast(list)
    local last = list.last
    if list.first > last then
        error("list is empty")
    local value = list[last]
    list[last] = nil
    list.last = last - 1
    return value
print("---------------------")
print("前面插入：")
local queue = listNew()
pushFirst(queue, 10)
pushFirst(queue, 5)
pushFirst(queue, 1)
---------------------------------------
--- 此时队列内容 1，5，10
---------------------------------------
print(popFirst(queue))      --> 1
print("---------------------")
print("后面插入：")
pushLast(queue, 15)
pushLast(queue, 20)
pushLast(queue, 30)
---------------------------------------
--- 此时队列内容 5，10，15，20，30
---------------------------------------
print(popLast(queue))       --> 30
print("---------------------")
print("输出全部：")
---------------------------------------
--- 此时队列内容 5，10，15，20
---------------------------------------
for k, v in pairs(queue) do
    print(k .. "-->" .. v)
--> -2-->5
--> -1-->10
--> first-->-2
--> 1-->20
--> 0-->15
--> last-->1
六、写在最后
Lua 项目地址：Github传送门  (如果对你有所帮助或喜欢的话，赏个star吧，码字不易，请多多支持)
如果觉得本篇博文对你有所启发或是解决了困惑，点个赞或关注我呀。
公众号搜索 “江澎涌”，更多优质文章会第一时间分享与你。