commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ismael Juma (JIRA)" <j...@apache.org>
Subject [jira] Commented: (MATH-230) Implement Sparse Matrix Support
Date Sun, 14 Dec 2008 01:38:44 GMT

    [ 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.


Mime
View raw message