This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.

The fourth edition targets Lua 5.3 and is available at Amazon and other bookstores.

By buying the book, you also help to support the Lua project.

Programming in Lua | ||

Part II. Tables and Objects Chapter 11. Data Structures |

There are two main ways to represent matrices in Lua.
The first one is to use an array of arrays,
that is, a table wherein each element is another table.
For instance, you can create a matrix of zeros with
dimensions `N`

by `M`

with the following code:

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 endBecause tables are objects in Lua, you have to create each row explicitly to create a matrix. On the one hand, this is certainly more verbose than simply declaring a matrix, as you do in C or Pascal. On the other hand, that gives you more flexibility. For instance, you can create a triangular matrix changing the line

for j=1,M doin the previous example to

for j=1,i doWith that code, the triangular matrix uses only half the memory of the original one.

The second way to represent a matrix in Lua is by composing the
two indices into a single one.
If the two indices are integers,
you can multiply the first one by a constant and then add
the second index.
With this approach,
the following code would create
our matrix of zeros with dimensions `N`

by `M`

:

mt = {} -- create the matrix for i=1,N do for j=1,M do mt[i*M + j] = 0 end end

If the indices are strings,
you can create a single index concatenating both indices
with a character in between to separate them.
For instance, you can index a matrix `m`

with string indices
`s`

and `t`

with the code `m[s..':'..t]`

,
provided that both `s`

and `t`

do not contain colons
(otherwise, pairs like (`"a:"`

, `"b"`

) and (`"a"`

, `":b"`

)
would collapse into a single index `"a::b"`

).
When in doubt,
you can use a control character like ``\0`

´
to separate the indices.

Quite often, applications use a *sparse matrix*,
a matrix wherein most elements are 0 or nil.
For instance, you can represent a graph by its adjacency matrix,
which has the value `x`

in position `m,n`

only when
the nodes `m`

and `n`

are connected with cost `x`

;
when those nodes are not connected,
the value in position `m,n`

is **nil**.
To represent a graph with ten thousand nodes,
where each node has about five neighbors,
you will need a matrix with a hundred million entries
(a square matrix with 10,000 columns and 10,000 rows),
but approximately only fifty thousand of them will not be **nil**
(five non-nil columns for each row,
corresponding to the five neighbors of each node).
Many books on data structures discuss at length
how to implement such sparse matrices without wasting 400 MB of memory,
but you do not need those techniques when programming in Lua.
Because arrays are represented by tables,
they are naturally sparse.
With our first representation
(tables of tables), you will need ten thousand tables,
each one with about five elements,
with a grand total of fifty thousand entries.
With the second representation,
you will have a single table,
with fifty thousand entries in it.
Whatever the representation,
you only need space for the non-nil elements.

Copyright © 2003–2004 Roberto Ierusalimschy. All rights reserved. |