commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Arne Ploese <aplo...@gmx.de>
Subject Re: [Math] "iterator" and "sparseIterator" in "RealVector" hierarchy
Date Wed, 17 Aug 2011 18:28:33 GMT
So what exactly is the meaning of isSparse?

* the vector at hand implements some kind of sparse storage? I.E:
OpenMapRealVector

or

* the vector is actually sparsely filled (then what is sparse anyway
10%, 50%, 90%?) in this case a SparserelVector interface is useless for
the compiler.

My suggestion is: ArrayRealVector implements a sparse iterator which
returns only values != 0? 

Having the backing storage implementation open, one could think of:

* isArray
* isBanded
* isSymetrical
* isDiagonal

as additional markers or put the whole thing in an enum or EnumSet?  

Am Mittwoch, den 17.08.2011, 08:51 -0700 schrieb Ted Dunning: 
> I think that all vectors and matrices should be able to answer the question
> about whether they are sparse and they should support sparse iterators,
> defaulting to the normal iterators in the general case.  So yes to the first
> question.  This allows the application programmer to be much less concerned
> about whether they are using a sparse or dense matrix without losing much
> performance, if any.
> 
> The second question I think is much less clear.  It might well be a good
> idea to keep the interface to help the compiler in cases where the
> programmer knows which general class of matrix they have.
> 
> On Wed, Aug 17, 2011 at 8:29 AM, Arne Ploese <aploese@gmx.de> wrote:
> 
> > Am Mittwoch, den 17.08.2011, 07:25 -0700 schrieb Ted Dunning:
> > > Arne,
> > >
> > > Please read the thread again.  I am providing an example of how I think
> > > things *should* be.
> > OK.
> > if I understand you right: isSparse() should be added to RealVector and
> > the interface SparseRealVector can be dropped?
> >
> > >
> > > The point of doing so is that things are not that way now.  Telling me
> > that
> > > they are not that way is pretty redundant.
> > >
> > > On Wed, Aug 17, 2011 at 2:37 AM, Arne Ploese <aploese@gmx.de> wrote:
> > >
> > > > Currently sparseIterator is only used in RealVector, no matrix class
> > > > will be affected, because there is no sparseIterator.
> > > > Search you sources for "sparseIterator" ?
> > > >
> > > > Arne
> > > > Am Dienstag, den 16.08.2011, 14:09 -0700 schrieb Ted Dunning:
> > > > > Here is an example from the perspective of somebody adding a new
kind
> > of
> > > > > matrix.
> > > > >
> > > > > Take the two kinds of matrix as RandomTrinaryMatrix(rows, columns,
p)
> > > > that
> > > > > has elements that are -1, 0 or 1.  1 and -1 have equal probabilities
> > of
> > > > p/2.
> > > > >  The value of p should be in [0,1].
> > > > >
> > > > > It would be very nice if the implementor of this matrix could extend
> > an
> > > > > abstract matrix and over-ride get() to generate a value and set()
to
> > > > throw
> > > > > an unsupported operation exception.  If p < 0.1, then the matrix
> > should
> > > > be
> > > > > marked as sparse, else as dense.
> > > > >
> > > > > All operations against other matrices, sparse or dense should work
> > well
> > > > > without any special handling by the implementor of this matrix.
> > > > >
> > > > > This works in Mahout for instance by having the default operations
in
> > > > > AbstractMatrix test for sparseness of left or right operands and
do
> > the
> > > > > right thing.  Obviously, a type test will not tell you whether this
> > > > matrix
> > > > > is sparse or not.
> > > > >
> > > > > This matrix and siblings is very important in compressed sensing
and
> > > > > stochastic projection algorithms.
> > > > >
> > > > > On Tue, Aug 16, 2011 at 1:55 PM, Phil Steitz <phil.steitz@gmail.com>
> > > > wrote:
> > > > >
> > > > > > On 8/16/11 4:46 AM, Gilles Sadowski wrote:
> > > > > > > Hi.
> > > > > > >
> > > > > > >> I understood what he was suggesting.  I still disagree.
 Dynamic
> > > > > > dispatch
> > > > > > >> and non-lattice typing structure is still required
to make this
> > all
> > > > > > work.
> > > > > > >>  Java doesn't really do that.  Pretending that what
Java does is
> > > > > > sufficient
> > > > > > >> is hammer-looking-for-a-nail, not solving the problems
at hand.
> > > > > > > Maybe that *I* don't understand what you are hinting at.
Sorry
> > for
> > > > being
> > > > > > > dense. [Although that seems appropriate in this discussion
:-).]
> > > > > > >
> > > > > > > Polymorphism provides dynamic dispatch, overloading does
not;
> > that's
> > > > why
> > > > > > my
> > > > > > > proposition is that when you manipulate "unknown" types,
those
> > should
> > > > > > come
> > > > > > > as "this", not as the argument of the method.
> > > > > > >
> > > > > > > What's wrong with that?
> > > > > > >
> > > > > > > As for "hammer-looking-for-a-nail", I also don't see what
you
> > mean:
> > > > What
> > > > > > is
> > > > > > > the problem? I guess that there are lots of applications
who
> > never
> > > > need
> > > > > > to
> > > > > > > know about sparse vectors/matrices. In those cases, the
added
> > > > complexity
> > > > > > is
> > > > > > > not a "feature". The issue reported contends that the current
> > design
> > > > in
> > > > > > CM
> > > > > > > can cause problems for dense implementations. I'm not even
sure
> > that
> > > > the
> > > > > > > current design is usable for the type of applications that
make
> > heavy
> > > > use
> > > > > > of
> > > > > > > sparseness. Those are problems, IMHO.
> > > > > >
> > > > > > I have been out of pocket the last couple of days and may not
have
> > > > > > time to dig into this until late tonight, but I agree with Gilles
> > > > > > that we need to get the conversation here more concrete.  I
know we
> > > > > > discussed this before and Ted and others had good examples
> > > > > > justifying the current setup.  Can we revisit these, please?
  What
> > > > > > would be great would be some examples both from the perspective
of
> > > > > > the [math] developer looking to add a new or specialized class
and
> > > > > > [math] users writing code that leverages the setup.
> > > > > >
> > > > > > Phil
> > > > > > >
> > > > > > >
> > > > > > > Gilles
> > > > > > >
> > > > > > >> On Mon, Aug 15, 2011 at 6:52 PM, Greg Sterijevski <
> > > > > > gsterijevski@gmail.com>wrote:
> > > > > > >>
> > > > > > >>> Forgive me for pushing my nose under the tent...
I couldn't
> > resist.
> > > > > > >>>
> > > > > > >>> I think Gilles is saying that each specialization
of the
> > > > matrix/vector
> > > > > > >>> objects would need to support pre (and post) multiplication
> > with a
> > > > > > dense.
> > > > > > >>> So
> > > > > > >>> the type issue would not be problematic.
> > > > > > >>>
> > > > > > >>> On Mon, Aug 15, 2011 at 6:34 PM, Ted Dunning <
> > > > ted.dunning@gmail.com>
> > > > > > >>> wrote:
> > > > > > >>>
> > > > > > >>>> No.
> > > > > > >>>>
> > > > > > >>>> You can't.  This is because the type is lost
as you enter the
> > > > generic
> > > > > > >>>> library.
> > > > > > >>>>
> > > > > > >>>> On Mon, Aug 15, 2011 at 4:28 PM, Gilles Sadowski
<
> > > > > > >>>> gilles@harfang.homelinux.org> wrote:
> > > > > > >>>>
> > > > > > >>>>>> They know that their own object is
dense, but they don't
> > know
> > > > what
> > > > > > >>> kind
> > > > > > >>>>> of
> > > > > > >>>>>> input they were given.  They should
still run fast if the
> > input
> > > > is
> > > > > > >>>>> sparse.
> > > > > > >>>>>
> > > > > > >>>>> Couldn't we still rely on polymorphism
by implementing
> > > > "preTimes":
> > > > > > >>>>>   unknown.preTimes(dense)
> > > > > > >
> > ---------------------------------------------------------------------
> > > > > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > > > > >
> > > > > > >
> > > > > >
> > > > > >
> > > > > >
> > ---------------------------------------------------------------------
> > > > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > > > >
> > > > > >
> > > >
> > > >
> > > >
> > > > ---------------------------------------------------------------------
> > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > >
> > > >
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > For additional commands, e-mail: dev-help@commons.apache.org
> >
> >



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message