[
https://issues.apache.org/jira/browse/MATH-230?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12656357#action_12656357
]
Ismael Juma commented on MATH-230:
----------------------------------
That was a tricky one. Luc, since you've done some changes to the code, it
might be easier for me to just paste the methods that have changed.
In OpenIntToDoubleHashMapTest, please add:
/**
* Regression test for a bug in findInsertionIndex where the hashing in the
second probing
* loop was inconsistent with the first causing duplicate keys after the
right sequence
* of puts and removes.
*/
public void testPutKeysWithCollisions() {
OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
int key1 = -1996012590;
double value1 = 1.0;
map.put(key1, value1);
int key2 = 835099822;
map.put(key2, value1);
int key3 = 1008859686;
map.put(key3, value1);
assertEquals(value1, map.get(key3));
assertEquals(3, map.size());
map.remove(key2);
double value2 = 2.0;
map.put(key3, value2);
assertEquals(value2, map.get(key3));
assertEquals(2, map.size());
}
/**
* Similar to testPutKeysWithCollisions() but exercises the codepaths in a
slightly
* different manner.
*/
public void testPutKeysWithCollision2() {
OpenIntToDoubleHashMap map = new OpenIntToDoubleHashMap();
int key1 = 837989881;
double value1 = 1.0;
map.put(key1, value1);
int key2 = 476463321;
map.put(key2, value1);
assertEquals(2, map.size());
assertEquals(value1, map.get(key2));
map.remove(key1);
double value2 = 2.0;
map.put(key2, value2);
assertEquals(1, map.size());
assertEquals(value2, map.get(key2));
}
and also update setUp to be like (I added some negative keys just in case):
@Override
protected void setUp() throws Exception {
javaMap.put(50, 100.0);
javaMap.put(75, 75.0);
javaMap.put(25, 500.0);
javaMap.put(Integer.MAX_VALUE, Double.MAX_VALUE);
javaMap.put(0, -1.0);
javaMap.put(1, 0.0);
javaMap.put(33, -0.1);
javaMap.put(23234234, -242343.0);
javaMap.put(23321, Double.MIN_VALUE);
javaMap.put(-4444, 332.0);
javaMap.put(-1, -2323.0);
javaMap.put(Integer.MIN_VALUE, 44.0);
/* Add a few more to cause the table to rehash */
javaMap.putAll(generate());
}
Run the tests and they should show at least one failure (I am not sure if the
second collisions test will fail with the version you have, but I added it to
verify a potential bug that I visually identified while modifying
findInsertionIndex).
Then change findInsertionIndex to be like:
private static int findInsertionIndex(int[] keys, byte[] states,
int key, int mask) {
int hash = hashOf(key);
int index = hash & mask;
if (states[index] == FREE)
return index;
else if (states[index] == FULL && keys[index] == key)
return changeIndexSign(index);
int perturb = perturb(hash);
int j = index;
if (states[index] == FULL) {
while (true) {
j = probe(perturb, j);
index = j & mask;
perturb >>= PERTURB_SHIFT;
if (states[index] != FULL || keys[index] == key)
break;
}
}
if (states[index] == FREE)
return index;
/*
* Due to the loop exit condition, if (states[index] == FULL) then
* keys[index] == key
*/
else if (states[index] == FULL)
return changeIndexSign(index);
int firstRemoved = index;
while (true) {
j = probe(perturb, j);
index = j & mask;
if (states[index] == FREE)
return firstRemoved;
else if (states[index] == FULL && keys[index] == key)
return changeIndexSign(index);
perturb >>= PERTURB_SHIFT;
}
}
All tests should pass after that. Nice catch by the way, it was a nasty bug.
> Implement Sparse Matrix Support
> -------------------------------
>
> Key: MATH-230
> URL: https://issues.apache.org/jira/browse/MATH-230
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 2.0
> Environment: N/A
> Reporter: Sujit Pal
> Assignee: Luc Maisonobe
> Priority: Minor
> Fix For: 2.0
>
> Attachments: math-230.diff, patch-2.txt,
> RealMatrixImplPerformanceTest.java, SparseRealMatrix.java,
> SparseRealMatrixTest.java
>
>
> I needed a way to deal with large sparse matrices using commons-math
> RealMatrix, so I implemented it. The SparseRealMatrixImpl is a subclass of
> RealMatrixImpl, and the backing data structure is a Map<Point,Double>, where
> Point is a struct like inner-class which exposes two int parameters row and
> column. I had to make some changes to the existing components to keep the
> code for SparseRealMatrixImpl clean. Here are the details.
> 1) RealMatrix.java:
> - added a new method setEntry(int, int, double) to set data into a matrix
> 2) RealMatrixImpl.java:
> - changed all internal calls to data[i][j] to getEntry(i,j).
> - for some methods such as add(), subtract(), premultiply(), etc, there
> was code that checked for ClassCastException and had two versions,
> one for a generic RealMatrix and one for a RealMatrixImpl. This has
> been changed to have only one that operates on a RealMatrix. The
> result is something like auto-type casting. So if:
> RealMatrixImpl.add(RealMatrix) returns a RealMatrixImpl
> SparseRealMatrixImpl.add(RealMatrix) returns a SparseRealMatrixImpl
> 3) SparseRealMatrixImpl added as a subclass of RealMatrixImpl.
> 4) LUDecompositionImpl changed to use a clone of the passed in RealMatrix
> instead of its data[][] block, and now it uses clone.getEntry(row,col)
> calls instead of data[row][col] calls.
> 5) LUDecompositionImpl returned RealMatrixImpl for getL(), getU(), getP()
> and solve(). It now returns the same RealMatrix impl that is passed
> in through its constructor for these methods.
> 6) New test for SparseRealMatrixImpl, mimics the tests in RealMatrixImplTest,
> 7) New static method to create SparseRealMatrixImpl out of a double[][] in
> MatrixUtils.createSparseRealMatrix().
> but using SparseRealMatrixImpl.
> 8) Verified that all JUnit tests pass.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
