11.2 矩阵和多维数组 |
Lua中有两种表示矩阵的方法,一是“数组的数组”。也就是说,table的每个元素是另一个table。例如,可以使用下面代码创建一个n行m列的矩阵:
mt = {} -- create the matrix
for i=1,N do
mt[i] = {} -- create a new row
for j=1,M do
mt[i][j] = 0
end
end
由于Lua中table是对象,所以每一行我们必须显式地创建一个table,比起c或pascal,这显得冗余,但另一方面也提供了更多的灵活性,例如可修改前面的例子创建一个三角矩阵:
for j=1,M do
改成
for j=1,i do
这样实现的三角矩阵比起整个矩阵,仅使用一半的内存空间。
表示矩阵的另一方法,是将行和列组合起来。如果索引下标都是整数,通过第一个索引乘于一个常量(列)再加上第二个索引,看下面的例子实现创建n行m列的矩阵:
mt = {} -- create the matrix
for i=1,N do
for j=1,M do
mt[i*M + j] = 0
end
end
如果索引是字符串,可用一个单字符将两个字符串索引连接起来构成一个单一的索引下标,例如一个矩阵m,索引下标为s和t,假定s和t都不包含冒号,代码为:m[s..':'..t],如果s或者t包含冒号将导致混淆,比如("a:", "b") 和("a", ":b"),当对这种情况有疑问的时候可以使用控制字符来连接两个索引字符串,比如'\0'。
实际应用中常常使用稀疏矩阵,稀疏矩阵指矩阵的大部分元素都为空或者0的矩阵。例如,我们通过图的邻接矩阵来存储图,也就是说:当m,n两个节点有连接时,矩阵的m,n值为对应的x,否则为nil。如果一个图有10000个节点,平均每个节点大约有5条边,为了存储这个图需要一个行列分别为10000的矩阵,总计10000*10000个元素,实际上大约只有50000个元素非空(每行有五列非空,与每个节点有五条边对应)。很多数据结构的书上讨论采用何种方式才能节省空间,但是在Lua中你不需要这些技术,因为用table实现的数据本身天生的就具有稀疏的特性。如果用我们上面说的第一种多维数组来表示,需要10000个table,每个table大约需要五个元素(table);如果用第二种表示方法来表示,只需要一张大约50000个元素的表,不管用那种方式,你只需要存储那些非nil的元素。