The
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 formula
indexIn1DArray = 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