# A “triangular” data structure for commutative relationships

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?

-

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.

-
Just wondering: that seems OK when you have e few rows, but can you actually nicely specify that the rows are of lengths, say, 1,2,3, ..., 1000? – Hendrik Jan Jul 4 '14 at 22:37
Sure. In C, you'd do it by allocating the rows individually using a for loop, rather than statically defining it the way you would for a rectangular m-by-n array. – David Richerby Jul 4 '14 at 22:40

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.

-
Personally, I think use formula to map 2-D position to 1-D position is better than sharing table. Especially when the 2 commutative function you're storing have different diagonals. – Billiska Jul 5 '14 at 13:34
If you use your formula to map 2-D position to 1-D position, what is the cost in access time, and what is the code size for one access, compared to standard accessing of a $n\times n$ array. cc @Billiska – babou Jul 5 '14 at 14:37
@babou I am about to post an example of that mapping as another answer. It's kind of f(x,y) = ((y+1)*(y))/2 + x which is so small a formula. It's almost the same as when you are accessing 2D array in some implementation, the command a[x][y] is actually translated to a[x*row_size + y]. – Billiska Jul 5 '14 at 14:54

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.

-
I have no doubt one can do it. I did something similar in the exemple cited in my answer. But my question is about the cost in code size in the machine. This is intended to save space. Does it really? What should various parameters be so that it does? How many "commutative relationships" are actually to be represented in the application? How large are they? How many occurences of an access are to be found in the code of the application? How often are they executed? How much space is taken by the access code for your implementation, and when using standard arrays? – babou Jul 5 '14 at 15:13
I thought we are more concerned about the data storage size, than the code storage size. Data size can grows to million, but code size is just that 4 more lines I wrote. Each time you access the array, just call a[f(x,y)] instead of a[x,y]. Or better yet, if I just let the function f returns the value in a directly, you can just call f(x,y) which uses 1 less character than a[x][y]. For an example of commutative relationship, try the 'friend' relationship of social network. – Billiska Jul 5 '14 at 15:18
The question was about commutative relationships. I have no idea how many will be used in the program. I am not saying that your proposal is wrong, but only asking when it is profitable to do so. Many users are beginners, and I do not assume they realize that some savings are expensive. Also I am not worried about source code size, but about compiled code. And that depends also on the programming language. If you consider the "friend" relationship of social networks, it is very big, but very sparse (very low graph density) and will call for very different implementations. – babou Jul 5 '14 at 20:37
@babou Do I understand correctly that your only concern is just that my answer is not explicit enough for beginners? In that case I'm welcoming your edits. – Billiska Jul 5 '14 at 21:02