A "triangular" data structure for commutative relationships

Question

A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, the same is true for any table that represents a commutative relationship. Is there a data structure that can take advantage of commutativity to avoid storing redundant values?

Answer 1

Some languages, such as C, support ragged arrays: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.

Answer 2

Sure, you can put all information (of half a table) in a linear array, and use a formula to compute the new position given the original arguments. That formula is quadratic, and you are basically changing space for speed.

The best thing to do however is looking for two tables that are symmetric (commutative operations) and of the same size, and share the space.

Answer 3

I want to expand on the other answers and give a concrete example of the 2-D index map to 1-D index.

Let $N = \{0,1,2,3,...\}$. Call our one-to-one map $f \colon N \times N \rightarrow N$.

First, let us list out some desirable properties $f$ should have.

1. $f$ is commutative. We want [x][y] and [y][x] to use same position in memory.
2. Small index maps to small index.
3. Since $f$ is a bijection to $N$, it gives an ordering to $N \times N$. We want this ordering to be meaningful. Say, order by the sum. If sum is equal, order by the larger element.
4. There is no gap in the index mapped, all destination index are used.

Or more mathematically:

1. $f(x,y) = f(y,x)$
2. If $x+y < a+b$ then $f(x,y) < f(a,b)$
3. If $x+y = a+b$, $x<y$, $a<b$ and $y<b$ then $f(x,y) < f(a,b)$
4. If $f(x,y) = k$ then $\exists x',y'. f(x',y') = k+1$
5. $f(0,0) = 0$

Here is an implementation in Python:

def f(x,y):
    if x > y:
        x,y = y,x
    return ((y+1)*(y))/2 + x

Test run:

for y in range(5):
    for x in range(y+1):
        print (x,y),'->',f(x,y)

gives:

(0, 0) -> 0
(0, 1) -> 1
(1, 1) -> 2
(0, 2) -> 3
(1, 2) -> 4
(2, 2) -> 5
(0, 3) -> 6
(1, 3) -> 7
(2, 3) -> 8
(3, 3) -> 9
(0, 4) -> 10
(1, 4) -> 11
(2, 4) -> 12
(3, 4) -> 13
(4, 4) -> 14

Let us show how this saves space:

First we consider the data storage space. Let $n$ be the largest index to be accessed.

If I use $n \times n$ array to store the commutative function, it would need $n^2$ units of space.

If I use 1 dimensional array to store the same data with this index mapping scheme, it would need $\frac{n(n+1)}{2}$ units of space.

Hence the data storage space saved is: $n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}{2} = O(n^2)$.

The increase in code storage size is $O(1)$ and can be overshadowed by the saving in data storage space. The increase in processing time is also $O(1)$ per access.

Answer 4

If you are willing to trade time for space, there are many ways to represent matrices (or other structures) satisfying specific constraints. Array of arrays, linked lists, etc. The choice of the representation also depends on what operations you intend to perform, with what frequency and statistics, either using the structure or modifying it (the most basic statement about data-structure choice). See for example this question (which I remember because I answered, and because the structure is unusual) : Algorithm: Dimension increase in 1D representation of Square Matrix.

Trading time for space, i.e. making some operations more costly in time in order to save space is not always a winning proposition. More complex access may mean more instructions inline every time the structure is accessed, which may sometimes make you lose more in code space than you gain in data space, while losing in time too.

Hence, if the dimension of you matrix remains small, and if you create few of them, it may be a wiser choice to simply waste the data space. Actually, it occasionally happens in some situations that one will chose to waste a bit of data space in order to simplify the code. One may even choose to waste a bit of space only to make the program more readable and easier to maintain.