4
\$\begingroup\$

Problem Statement:

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums

dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Questions:

I have written the following code using Hashmap to calculate the dot product for sparse vectors. Compared to using an array, this method seems faster. But I want to get some opinions on hashmap solution in terms of scalability. My point is that if my nums array is very large (billions), I can get hash collisions and my hash bucket's linkedlist may become longer. Plus, I may have to resize my hashmap periodically while traversing the nums array. Also, in real-life, my memory tends to be limited, which may worsens the runtime complexity of hashmap approach. Comparing to the array approach, I feel that we can simply use map-reduce or parallel programming to calculate the dot product. Therefore, I feel the array based approach may be better in terms of scalability. Please give me some pointers about it.

HashMap Method

class SparseVector {
    
    
    HashMap<Integer, Integer> sparseVec;
    
    SparseVector(int[] nums) {
        sparseVec = new HashMap<>();
        
        for(int i =0;i<nums.length;i++){
            if(nums[i] > 0){
                sparseVec.put(i, nums[i]);
            }
        }
    }
    
    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        
        HashMap<Integer, Integer> othvec = vec.sparseVec;
        
        // get the keyList of that sparseVec
        List<Integer> othKeyList = new ArrayList<>(othvec.keySet());
        
        int dotProduct = 0;
        for(int i = 0;i<othKeyList.size();i++){
            int nonZeroIndex = othKeyList.get(i);
            if(this.sparseVec.containsKey(nonZeroIndex)){
                dotProduct += (this.sparseVec.get(nonZeroIndex) *
                              othvec.get(nonZeroIndex));
            }
        }
        
        return dotProduct;
        
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);

Array method

class SparseVector {

    private int[] array;

    SparseVector(int[] nums) {
        array = nums;
    }

    public int dotProduct(SparseVector vec) {
        int result = 0;

        for (int i = 0; i < array.length; i++) {
            result += array[i] * vec.array[i];
        }
        return result;
    }   
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ A hash map is not the right way to store a sparse vector. Use an array of (index, value) pairs, the array is sorted by index. This is much more efficient for computation. The dictionary is more efficient when modifying the array, but you don’t modify any arrays. \$\endgroup\$ Commented Mar 31 at 14:07
  • 1
    \$\begingroup\$ Also, a plain array is possibly faster, depending on the number of zero entries. The big advantage of sparse representation is the reduced memory use. \$\endgroup\$ Commented Mar 31 at 14:16
  • \$\begingroup\$ @CrisLuengo If the array is sufficiently sparse, and access is random enough, the theoretically constant-time access would have a lot of page faults. These might be slower than a binary search of a compressed sparse representation that fits into cache. \$\endgroup\$
    – Davislor
    Commented Mar 31 at 21:39
  • \$\begingroup\$ @Davislor I guess I’m biased, thinking of linear algebra, where there’s no random access ever. \$\endgroup\$ Commented Mar 31 at 22:05

3 Answers 3

2
\$\begingroup\$

Partly this depends on how sparse the vectors truly are. Obviously, for extremely dense vectors the array method will be faster, and for extremely sparse vectors the map method will be faster; the crossover would have to be determined via benchmark.

There are some easy wins:

Make sparseVec final.

You may want to use a TreeMap. In my imagination (not tested), it stands a better chance at being able to quickly partition into balanced sub-trees when the spliterator is asked to back a parallel stream.

Don't force the user to pass in a dense array! You can accept a map directly (shown), with a subordinate utility constructor to make the map (not shown).

An easy optimisation is to ensure that, when there are two vectors of non-equal population size, iterate on the smaller of the two. Imagine performing the dot product of two nominally 10,000,000-length vectors, where the first has three non-zeros and the second has no zeros at all.

Don't if on a containsKey because that costs a double lookup. Instead use getOrDefault; the unconditional multiplication will likely be less costly.

Add unit tests. I demonstrate one way.

There are many other implementation variants; you could -

  • Perform set intersection on the left and right key sets before iteration, or not;
  • Apply a range subMap on the right-hand set before iteration, or not;
  • Perform the set intersection on the sequenced view of the key set, or not.

etc.

Some possible implementations

package com.stackexchange;

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.*;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

public class Main {
    public static abstract class SparseVector {
        protected final SortedMap<Integer, Integer> vec;

        protected SparseVector(Map<Integer, Integer> vec) {
            this.vec = new TreeMap<>(vec);
        }

        public abstract int dot(SparseVector other);
    }

    public static class SparseVectorStream extends SparseVector {
        public SparseVectorStream(Map<Integer, Integer> vec) {
            super(vec);
        }

        private int dotDefault(
            Map<Integer, Integer> left,
            Map<Integer, Integer> right
        ) {
            return left.entrySet()
                .parallelStream()
                .mapToInt(
                    kv ->
                        kv.getValue() *
                            right.getOrDefault(kv.getKey(), 0)
                )
                .sum();
        }

        public int dot(SparseVector other) {
            // Iterate over the smaller of the two entry sets
            if (vec.size() < other.vec.size())
                return dotDefault(vec, other.vec);
            return dotDefault(other.vec, vec);
        }
    }

    public static class SparseVectorIntersection extends SparseVector {
        public SparseVectorIntersection(Map<Integer, Integer> vec) {
            super(vec);
        }

        public int dot(SparseVector other) {
            Set<Integer> intersection = new TreeSet<>(vec.keySet());
            intersection.retainAll(other.vec.keySet());
            if (intersection.isEmpty())
                return 0;

            return intersection
                .parallelStream()
                .mapToInt(
                    k -> vec.get(k) * other.vec.get(k)
                )
                .sum();
        }
    }

    public static class SparseVectorSubmap extends SparseVector {
        public SparseVectorSubmap(Map<Integer, Integer> vec) { super(vec); }

        public int dot(SparseVector other) {
            SortedSet<Integer> intersection = new TreeSet<>(vec.sequencedKeySet());
            intersection.retainAll(other.vec.keySet());
            if (intersection.isEmpty())
                return 0;

            // This will (sometimes only partially) reduce the left and right maps
            // Alternative: benchmark without doing this, or reducing the greater
            // of the two keysets
            Integer first = intersection.first(),
                last = intersection.last() + 1;
            SortedMap<Integer, Integer>
                left = vec.subMap(first, last),
                right = other.vec.subMap(first, last);

            return intersection
                .parallelStream()
                .mapToInt(
                    k -> left.get(k) * right.get(k)
                )
                .sum();
        }
    }

    @Nested
    class Tests {
        private <TVector extends SparseVector>
        Map.Entry<
            String, Map.Entry<SparseVector, SparseVector>
        > create(
            Map<Integer, Integer> vleft,
            Map<Integer, Integer> vright,
            Class<TVector> clazz
        ) {
            Constructor<TVector> cons;
            try {
                cons = clazz.getDeclaredConstructor(Map.class);
            } catch (NoSuchMethodException e) {
                throw new RuntimeException(e);
            }

            try {
                return Map.entry(
                    clazz.getName(),
                    Map.entry(cons.newInstance(vleft), cons.newInstance(vright))
                );
            } catch (InstantiationException | IllegalAccessException | InvocationTargetException e) {
                throw new RuntimeException(e);
            }
        }

        private Map<
            String,
            Map.Entry<SparseVector, SparseVector>
        > implementations(
            Map<Integer, Integer> left,
            Map<Integer, Integer> right
        ) {
            return Map.ofEntries(
                create(left, right, SparseVectorStream.class),
                create(left, right, SparseVectorIntersection.class),
                create(left, right, SparseVectorSubmap.class)
            );
        }

        @Test
        void smallVectors() {
            for (var lr: implementations(
                Map.of(0, 0),
                Map.of(1, 1)
            ).values()) {
                assertEquals(0, lr.getKey().dot(lr.getValue()));
            }

            for (var lr: implementations(
                Map.of(0, 0, 1, 1),
                Map.of(0, 1, 1, 1)
            ).values()) {
                assertEquals(1, lr.getKey().dot(lr.getValue()));
            }

            for (var lr: implementations(
                Map.of(0, 1, 5000, 2),
                Map.of(1, 0, 5000, 3)
            ).values()) {
                assertEquals(6, lr.getKey().dot(lr.getValue()));
            }

            for (var lr: implementations(
                Map.of(0, 1, 5000, 1),
                Map.of(1, 1, 5001, 1)
            ).values()) {
                assertEquals(0, lr.getKey().dot(lr.getValue()));
            }
        }

        @Test
        void bigVector() {
            Random rand = new Random(0);

            TreeMap<Integer, Integer> left = new TreeMap<>(), right = new TreeMap<>();
            for (int i = 0; i < 10_000; ++i) {
                left.put(
                    rand.nextInt(0, 20_000),
                    rand.nextInt(0, 5)
                );
                right.put(
                    rand.nextInt(0, 20_000),
                    rand.nextInt(0, 5)
                );
            }

            int reference = -1;
            for (var lr: implementations(left, right).values()) {
                int dot = lr.getKey().dot(lr.getValue());
                if (reference == -1)
                    reference = dot;
                else
                    assertEquals(reference, dot);
            }
        }
    }

    public static void main(String[] args) {

    }
}
\$\endgroup\$
2
\$\begingroup\$

Questions: I have written the following code using Hashmap to calculate the dot product for sparse vectors. Compared to using an array, this method seems faster. But I want to get some opinions on hashmap solution in terms of scalability. My point is that if my nums array is very large (billions), I can get hash collisions and my hash bucket's linkedlist may become longer. Plus, I may have to resize my hashmap periodically while traversing the nums array. Also, in real-life, my memory tends to be limited, which may worsens the runtime complexity of hashmap approach. Comparing to the array approach, I feel that we can simply use map-reduce or parallel programming to calculate the dot product. Therefore, I feel the array based approach may be better in terms of scalability. Please give me some pointers about it.

That's a lot of a question. I am confused about it. I think it is an XY problem to be solved, hence instead of trying to scale the solution from description, here is what I think you need. I think you need stream operations (filter, map) while working with arrays of primitives to avoid boxing and unboxing overhead required when using collections this way, reducing memory consumption and improving algorithm efficiency. Following code snippet implements stream operations for arrays of int values:

public class Sparse {

    private interface Operator {

        Sparse.Operator NOOP = (left, right) -> 0;
        Sparse.Operator ADDITION = (left, right) -> left + right;
        Sparse.Operator SUBSTRACTION = (left, right) -> left - right;
        Sparse.Operator MULTIPLICATION = (left, right) -> left * right;
        Sparse.Operator DIVISION = (left, right) -> left / right;
        
        int apply(int left, int right);
    }

    public interface Mapper {
        
        Sparse.Mapper EMPTY = (left, right) -> 0;
        
        int apply(int left, int right);
    }

    public interface  Filter {
        
        Sparse.Filter EMPTY = (left, right) -> true;
        
        boolean apply(int left, int right);
    }

    private static final int[] EMPTY_ARRAY = new int[] {};
    private int[] left;
    private int[] right;
    private Sparse.Filter filter;
    private Sparse.Mapper mapper;
    private Sparse.Operator operator;

    private Sparse(int[] left, int[] right) {
        this.left = (left == null) ? EMPTY_ARRAY : left;
        this.right = (right == null) ? EMPTY_ARRAY : right;
        this.filter = Sparse.Filter.EMPTY;
        this.mapper = Sparse.Mapper.EMPTY;
        this.operator = Sparse.Operator.NOOP;
    }

    public static Sparse join(int[] left, int[] right) {

        return new Sparse(left, right);
    }

    public Sparse filter(Sparse.Filter filter) {
        this.filter = filter;
        return this;
    }

    public Sparse map(Sparse.Mapper mapper) {
        this.mapper = mapper;
        return this;
    }
    
    public int addition() {
        this.operator = Sparse.Operator.ADDITION;
        return this.apply();
    }
    public int substract() {
        this.operator = Sparse.Operator.SUBSTRACTION;
        return this.apply();
    }
    public int multiplication() {
        this.operator = Sparse.Operator.MULTIPLICATION;
        return this.apply();
    }
    public int division() {
        this.operator = Sparse.Operator.DIVISION;
        return this.apply();
    }
    
    private int apply() {
        int[] values = left;
        int[] mappings = right;
        int result = 0;
        
        if ( left.length > right.length ) {
            values = right;
            mappings = left;
        }
        for ( int i = 0; i < values.length; i++ ) {
            if (this.filter.apply(values[i], mappings[i]) ) {
                result += this.mapper.apply(values[i], mappings[i]);
                result = this.operator.apply(result
                                            , this.mapper.apply(values[i]
                                                               , mappings[i]));
            }
        }
        
        return result;
    }
}

... and following a shallow test class for it that before compiling and running it it needs values for the two arrays of int, values and multipliers...

public class SparseTest {

    public static void main(String[] args) {
        int[] values = new int[] { ... };
        int[] multipliers = new int[] { ... };

        int sum = Sparse.join(values, multipliers)
                        .filter((left, right) -> left > 0 && right > 0)
                        .map((left, right) -> left * right)
                        .addition();

        System.out.println(sum);
        
    }
}
\$\endgroup\$
2
\$\begingroup\$

My point is that if my nums array is very large (billions)

Then probably nums aren't stored in memory and it might not be possible to store it in memory, probably nums aren't an array. The processing of a that large series of int values "(billions)" has to be incremental, reading nums one at a time processing the read value and dispatching it. That is something achievable with an Iterator. Following code snippet is a solution mimicking Iterator, in that it defines an interface, called Source, with just next method returning primitive type int value:

public class SourcedSparse {

    public static interface Source { int next(); }

    public interface Mapper {

        SourcedSparse.Mapper EMPTY = (left, right) -> 0;

        int apply(int left, int right);
    }

    public interface Filter {

        SourcedSparse.Filter EMPTY = (left, right) -> true;

        boolean apply(int left, int right);
    }

    private static final Source EMPTY_SOURCE = () -> 0;
    private SourcedSparse.Source left;
    private SourcedSparse.Source right;
    private SourcedSparse.Filter filter;
    private SourcedSparse.Mapper mapper;

    {
        this.filter = SourcedSparse.Filter.EMPTY;
        this.mapper = SourcedSparse.Mapper.EMPTY;
    }

    private SourcedSparse(SourcedSparse.Source left
                        , SourcedSparse.Source right) {
        this.left = (left == null) ? EMPTY_SOURCE : left;
        this.right = (right == null) ? EMPTY_SOURCE : right;
    }

    private SourcedSparse(SourcedSparse.Source left) {
        this(left, null);
    }

    public static SourcedSparse joining(Source left, Source right) {

        return new SourcedSparse(left, right);
    }

    public static SourcedSparse vector(Source left) {
        return new SourcedSparse(left);
    }

    public SourcedSparse filter(SourcedSparse.Filter filter) {
        this.filter = filter;
        return this;
    }

    public SourcedSparse map(SourcedSparse.Mapper mapper) {
        this.mapper = mapper;
        return this;
    }

    public int next() {
        int value = this.left.next();
        int mapping = this.right.next();
        int result = 0;
        if (this.filter.apply(value, mapping)) {
            result = this.mapper.apply(value, mapping);

        }
        return result;
    }
}

...and following a test suite for incremental read of values, defining a Source interface implementation with an additional hasNext method, called IntSource. A Source implementation used for real life use cases could be backed by an java.io.InputStream that reads values from an external environment:

public class SourcedSparseTest {

    public static void main(String[] args) {
        SourcedSparseTest test = new SourcedSparseTest();
        test.addition();
        test.substraction();
        test.partialSubstraction();
        test.multiplication();
        test.divistion();
    }

    public void addition() {
        IntSource values = intSource(1, 5, 4, 8, 12, 17);
        IntSource multipliers = intSource(21, 15, 84, 8, 2, 7);
        SourcedSparse sparse = SourcedSparse.joining(values, multipliers)
                                            .filter((left, right) -> left > 0
                                                                  && right > 0)
                                            .map((left, right) -> left * right);
        int addition = 0;
        while (values.hasNext()) { addition += sparse.next(); }
        
        close(values);
        close(multipliers);

        System.out.println("addition: " + addition);
    }

    public void partialSubstraction() {
        int[] intArray = { 1, 5, 4, 8, 12, 17 };
        IntSource values = intSource(intArray);
        IntSource multipliers = intSource(21, 15, 84, 8, 2, 7);
        SourcedSparse sparse = SourcedSparse.joining(values, multipliers)
                                            .filter((left, right) -> left > 0
                                                                  && right > 0)
                                            .map((left, right) -> left * right);
        int bound = intArray.length/2 + 1;
        int index = 0;
        int substraction = 0;
        while ( ++index < bound) { substraction -= sparse.next(); }
        
        close(values);
        close(multipliers);

        System.out.println("substraction of " + (index - 1)
                         + " values: " + substraction);
    }

    public void substraction() {
        IntSource values = intSource(1, 5, 4, 8, 12, 17);
        IntSource multipliers = intSource(21, 15, 84, 8, 2, 7);
        SourcedSparse sparse = SourcedSparse.joining(values, multipliers)
                                            .filter((left, right) -> left > 0
                                                                  && right > 0)
                                            .map((left, right) -> left * right);
        int substraction = 0;
        while ( values.hasNext() ) { substraction -= sparse.next(); }
        
        close(values);
        close(multipliers);
        
        System.out.println("substraction: " + substraction);
    }

    public void multiplication() {
        IntSource values = intSource(1, 5, 4, 8, 12, 17);
        IntSource multipliers = intSource(21, 15, 84, 8, 2, 7);
        SourcedSparse sparse = SourcedSparse.joining(values, multipliers)
                                            .filter((left, right) -> left > 0
                                                                  && right > 0)
                                            .map((left, right) -> left * right);
        long multiplication = sparse.next();
        while (values.hasNext()) {
            int next = sparse.next();
            if (next > 0) { multiplication *= next; }
        }
        
        close(values);
        close(multipliers);

        System.out.println("multiplication: " + multiplication);
    }

    public void divistion() {
        IntSource values = intSource(1, 5, 4, 8, 12, 17);
        IntSource multipliers = intSource(21, 15, 84, 8, 2, 7);
        SourcedSparse sparse = SourcedSparse.joining(values, multipliers)
                                            .filter((left, right) -> left > 0
                                                                  && right > 0)
                                            .map((left, right) -> left * right);
        double division = sparse.next();
        while (values.hasNext()) {
            int next = sparse.next();
            if (next > 0) { division /= next; }
        }
        
        close(values);
        close(multipliers);

        System.out.println("division: " + division);
    }
    
    private static class IntSource implements SourcedSparse.Source
                                            , AutoCloseable {

        private java.util.Scanner scanner;
        
        public IntSource(java.util.Scanner scanner) { this.scanner = scanner; }
        
        @Override
        public void close() throws Exception { this.scanner.close(); }

        @Override
        public int next() { return this.scanner.nextInt(); }
        
        public boolean hasNext() { return this.scanner.hasNext(); }
    }
    
    private IntSource intSource(int... values) {
        StringBuilder stringBuilder = new StringBuilder(values[0]);
        for ( int i = 1; i < values.length; i++ ) {
            stringBuilder.append(" ").append(values[i]);
        }
        return new IntSource(new java.util.Scanner(stringBuilder.toString()));
    }

    private void close(AutoCloseable autoclosable) {
        try {
            autoclosable.close();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

...outputing:

addition: 618
substraction: -618
substraction of 3 values: -475
multiplication: 4606156800
division: 1.2211916016406563E-6
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.