Page 1 of 1

Sap: why does it use triangular matrix ?

Posted: Thu Apr 24, 2014 2:43 pm
Hi, in line 186 of this code file :
it uses triangular matrix, why can't we use HashTable instead of that?
i can't understand these lines :

Code: Select all

` if (current.id > test.id) {      matrix[test.id + (current.id * (current.id - 1) / 2)] = true;} else {      matrix[current.id + (test.id * (test.id - 1) / 2)] = true;}`

and why we should check their id ?

Thanks

Re: Sap: why does it use triangular matrix ?

Posted: Thu Apr 24, 2014 8:06 pm
The
SemiSober wrote:Hi, in line 186 of this code file :
it uses triangular matrix, why can't we use HashTable instead of that?

It's using an upper packed storage mode array to store the triangular matrix. In the Java programming language a 2D array is actually an array of arrays (also called a jagged array) and as a result, not as efficient. In addition, storing the possible collision pairs only requires a triangular portion of a 2D array. Instead, its much more efficient to use a 1D array that uses a calculation to index the triangular matrix elements. From the source, the element Aij can be found by doing this:

Code: Select all

`// i and j are the row/column indices// we compute the 1D array index using a formulaindexIn1DArray = i + (j * (j - 1) / 2);Aij = array1d[indexIn1DArray];`

Using a HashTable would work of course, but there's no need. We already have O(1) lookup time for the 1D array since we compute the index.

SemiSober wrote:i can't understand these lines :
CODE: SELECT ALL
if (current.id > test.id) {
matrix[test.id + (current.id * (current.id - 1) / 2)] = true;
} else {
matrix[current.id + (test.id * (test.id - 1) / 2)] = true;
}

This is the calculation of the 1D index of the 2D element. In other words, its setting the Aij element to true.

and why we should check their id ?

We check which id (index) is bigger because the calculation works only when j >= i.

William

Re: Sap: why does it use triangular matrix ?

Posted: Fri Apr 25, 2014 12:48 am
Thanks, i think i got it now