Which is the best way to implement a sparse vector

Question

Which is the best way to implement a sparse vector in Java?

Of course the good thing would be to have something that can be manipulated quite easily (normalization, scalar product and so on)

Thanks in advance

Answer 1

MTJ has a Sparse Vector class. It has norm functions (1-norm 2-norm and ∞-norm) and dot product functions.

Answer 2

You can also try to look at la4j's CompressedVector implementation. It uses pair of arrays: array of values and array of their indicies. And with binary search on top of that it just flies. So, this implementation guarantees O(log n) running time for get/set operations.

Just a brief example

Vector a = new CompressedVector(new double[]{ 1.0, 2.0, 3.0 }).

// calculates L_1 norm of the vector
double n = a.norm();

// calculates the sum of vectors elements
double s = a.fold(Vectors.asSumAccumulator(0.0));

Answer 3

JScience has a SparseVector implementation that is part of its linear algebra package.