< Blog:Limbo(Redirected from Blog:Memory Leak/Triangular Matrices)

A triangular matrix is useful when you need to intersect data from two instances of the same list of objects, and the two operands are commutative (e.g. **x×y** = **y×x**) like the distance of every two cities on a map. You can save some space and processing time if you use a triangular matrix, since you need only to calculate half of the table.

For one of my current projects, I had to create and store a triangular matrix of arbitrary size, using as little memory as possible. To avoid too much unused space, I decided to store the matrix as an one-dimensional array. I spent some time to figure how to calculate the size of this array and how to find the offset of a given (**x**, **y**) pair. Here are the results.

Size: 4×4=16 |
→ |
Size: 1×6=6 |

Given an n×n matrix, the size s of its associated one-dimension array is:

Given x and y, indices of the original matrix and y > x (since it is triangular), the index i of the element on the associated one-dimension array is: