Programming in Lua : 11.2

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

11.2 – Matrices and Multi-Dimensional Arrays

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
    end

Because 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 do

in the previous example to

      for j=1,i do

With 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.