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] Issue Comment Edited: (MATH-230) Implement Sparse Matrix Support
Date Sun, 14 Dec 2008 15:39:44 GMT

    [ https://issues.apache.org/jira/browse/MATH-230?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12656396#action_12656396
] 

ijuma edited comment on MATH-230 at 12/14/08 7:38 AM:
------------------------------------------------------------

Thanks for committing this Luc. Good point about specialised implementations of add and subtract.
However, the current implementation has a lot of overhead due to the allocation of Entry objects.
Since the iterator doesn't implement java.util.Iterator anyway, we can do better by using
an iterator similar to Trove's. I will paste part of the javadoc below:

{code:java}
/**
 * Iterator for maps of type int and double.
 *
 * <p>The iterator semantics for Trove's primitive maps is slightly different
 * from those defined in <tt>java.util.Iterator</tt>, but still well within
 * the scope of the pattern, as defined by Gamma, et al.</p>
 *
 * <p>This iterator does <b>not</b> implicitly advance to the next entry
when
 * the value at the current position is retrieved.  Rather, you must explicitly
 * ask the iterator to <tt>advance()</tt> and then retrieve either the <tt>key()</tt>,
 * the <tt>value()</tt> or both.  This is done so that you have the option, but
not
 * the obligation, to retrieve keys and/or values as your application requires, and
 * without introducing wrapper objects that would carry both.  As the iteration is
 * stateful, access to the key/value parts of the current map entry happens in
 * constant time.</p>
 *
 * <p>In practice, the iterator is akin to a "search finger" that you move from
 * position to position.  Read or write operations affect the current entry only and
 * do not assume responsibility for moving the finger.</p>
 *
 * <p>Here are some sample scenarios for this class of iterator:</p>
 *
 * <pre>
 * // accessing keys/values through an iterator:
 * for (TIntDoubleIterator it = map.iterator();
 *      it.hasNext();) {
 *   it.advance();
 *   if (satisfiesCondition(it.key()) {
 *     doSomethingWithValue(it.value());
 *   }
 * }
 * (snipped)
 */
{code}

Shall I file a separate issue for that?

      was (Author: ijuma):
    Thanks for committing this Luc. Good point about specialised implementations of add and
subtract. However, the current implementation has a lot of overhead due to the allocation
of Entry objects. Since the iterator doesn't implement java.util.Iterator anyway, we can do
better by using an iterator similar to Trove's. I will paste part of the javadoc below:

{code:java}
/**
 * Iterator for maps of type int and double.
 *
 * <p>The iterator semantics for Trove's primitive maps is slightly different
 * from those defined in <tt>java.util.Iterator</tt>, but still well within
 * the scope of the pattern, as defined by Gamma, et al.</p>
 *
 * <p>This iterator does <b>not</b> implicitly advance to the next entry
when
 * the value at the current position is retrieved.  Rather, you must explicitly
 * ask the iterator to <tt>advance()</tt> and then retrieve either the <tt>key()</tt>,
 * the <tt>value()</tt> or both.  This is done so that you have the option, but
not
 * the obligation, to retrieve keys and/or values as your application requires, and
 * without introducing wrapper objects that would carry both.  As the iteration is
 * stateful, access to the key/value parts of the current map entry happens in
 * constant time.</p>
 *
 * <p>In practice, the iterator is akin to a "search finger" that you move from
 * position to position.  Read or write operations affect the current entry only and
 * do not assume responsibility for moving the finger.</p>
 *
 * <p>Here are some sample scenarios for this class of iterator:</p>
 *
 * <pre>
 * // accessing keys/values through an iterator:
 * for (TIntDoubleIterator it = map.iterator();
 *      it.hasNext();) {
 *   it.advance();
 *   if (satisfiesCondition(it.key()) {
 *     doSomethingWithValue(it.value());
 *   }
 * }
 * (snipped)
 */

Shall I file a separate issue for that?
  
> 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