Also, for matrices, is the internal storage optimized for row-major access or column-major access? Perhaps you can get a sparse iterator over the major dimension which returns a dense iterator over the minor, or a sparse iteator over all cells. What you expose boils down to what it is about the matrix or vector that you need to discover to be able to implement binary ops efficiently enough. As Java doesn't have multiple-dispatch, I don't really know a completely clean way to deal with this.
I also agree with Ted. The contract for sparse iteration should be that it can optionally skip returning zero entries. There may be cases when it's cheaper to store some zeros even if you use some sort of skip-list structure internally. Matthew On 17 August 2011 19:28, Arne Ploese <aplo...@gmx.de> wrote: > 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 <aplo...@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 <aplo...@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.ste...@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 < > > > > > > > gsterijev...@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.dunn...@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 < > > > > > > > >>>> gil...@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-unsubscr...@commons.apache.org > > > > > > > > For additional commands, e-mail: dev-h...@commons.apache.org > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > --------------------------------------------------------------------- > > > > > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > > > > > > > For additional commands, e-mail: dev-h...@commons.apache.org > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > --------------------------------------------------------------------- > > > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > > > > > For additional commands, e-mail: dev-h...@commons.apache.org > > > > > > > > > > > > > > > > > > > > > > --------------------------------------------------------------------- > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > > > For additional commands, e-mail: dev-h...@commons.apache.org > > > > > > > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > > -- Dr Matthew Pocock Visitor, School of Computing Science, Newcastle University mailto: turingatemyhams...@gmail.com gchat: turingatemyhams...@gmail.com msn: matthew_poc...@yahoo.co.uk irc.freenode.net: drdozer tel: (0191) 2566550 mob: +447535664143
