patternMinor
A "triangular" data structure for commutative relationships
Viewed 0 times
commutativeforstructurerelationshipsdatatriangular
Problem
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?
Solution
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.
Context
StackExchange Computer Science Q#28221, answer score: 8
Revisions (0)
No revisions yet.