Lua - Sparse Tables

A table is very versatile datastructure and can be used to represent a sparse array or a sparse matrix.

Sparse Array Implmentation using Table

In sparse array, we can consider a case, where most of entries are nil and few indexed entries are non-zero as shown below:

main.lua

sparseArray = {[2] = "apple", [8] = "orange", [11] = "banana" }

for i = 1, 12, 1
do
   print(i, sparseArray[i])
end

Output

When we run the above code, we will get the following output−

1	nil
2	apple
3	nil
4	nil
5	nil
6	nil
7	nil
8	orange
9	nil
10	nil
11	banana
12	nil

Sparse Matrix Implmentation using Table

A sparse matrix can be implmented as a multidimensional arrays using table with nil entries. As in lua array, data is stored based on indices it is possible to place the elements in a sparse way and it is the way Lua implementation of a matrix works. Since it does not store nil values in Lua, it is possible to save lots of memory without any special technique in Lua as compared to special techniques used in other programming languages.

Example - Creating Sparse Matrix

An example for matrix is shown below using manipulating indices.

main.lua

-- initialize a matrix
sparseMatrix = {}
-- max rows
rows = 3
-- min rows
columns = 3

sparseMatrix[1 * 3 + 1] = 1
sparseMatrix[1 * 3 + 2] = 1

sparseMatrix[2 * 3 + 1] = 1
sparseMatrix[2 * 3 + 2] = 1

-- print the matrix
for i=1,rows do
   for j=1,columns do
      print(i,j,sparseMatrix[i*columns + j])
   end
end

Output

When we run the above code, we will get the following output−

1	1	1
1	2	1
1	3	nil
2	1	1
2	2	1
2	3	nil
3	1	nil
3	2	nil
3	3	nil