sparse vectors increase tree creation speed by 400x

This is a tiny change to allow the usage of sparse vectors (http://en.wikipedia.org/wiki/Sparse_vector) and it has huge speed implications. To demonstrate these I've created SparseVectorTest.java if you run it you will get something like:

Training with sparse vectors took: 4 milliseconds
true=0.503 false=0.497 
Training with dense vectors took: 1650 milliseconds
true=0.503 false=0.497 
interesting indeed. I had entered:

https://github.com/sanity/quickdt/issues/21

as I used to get an exception for values not specified. For some reason I
am not getting that exception anymore ... that was the whole reason for
branching!


On Mon, Jun 23, 2014 at 4:48 PM, Chris Reeves <notifications@github.com>
wrote:

> In src/test/java/quickdt/SparseVectorTest.java:
>
> > +
> > +    @Test
> > +    public void sparse()  {
> > +
> > +        Random r = new Random();
> > +        LinkedList<Instance> trainSparseVectors = new LinkedList();
> > +        LinkedList<Instance> trainDenseVectors = new LinkedList();
> > +
> > +        for (int instance = 0; instance < 1000; instance++) {
> > +            HashMapAttributes sparseInstanceHmAttributes = new HashMapAttributes();
> > +            HashMapAttributes denseInstanceHmAttributes = new HashMapAttributes();
> > +            for (int feat = 0; feat < 1000; feat++) {
> > +                String key = ((Integer)feat).toString();
> > +//                String key = featureExtractionPipeline.getFeatureName((Integer)e.getKey());
> > +                if(feat == instance){
> > +                    denseInstanceHmAttributes.put(key, 1.0);
>
> Running this test 2 very different trees are built, as you are supplying 2
> very different data sets. TreeBuilder will use a default value of 0 for
> numeric attributes if no value is present. To verify this revert your
> change to HashMapAttributes and run your test again, I would suspect you
> will see similar build times and models for the sparse data set. By doing
> this in TreeBuilder we don't force all PredictiveModelBuilders to behave
> this way, also we can use a different default value for a Categorical
> attribute.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/sanity/quickdt/pull/35/files#r14099154>.
>