jsat.linear

Class SparseVector

java.lang.Object

jsat.linear.Vec

jsat.linear.SparseVector

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<IndexValue>

public class SparseVector
extends Vec

Provides a vector implementation that is sparse. It does not allocate space for a vector of the specified size, and only stores non zero values. All values not stored are implicitly zero.
Operations that change several zero values in a sparse vector to non-zero values may have degraded performance.
Sparce vector should never be used unless at least half the values are zero. If more then half the values are non-zero, it will use more memory then an equivalent DenseVector. The more values that are zero in the vector, the better its performance will be.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
SparseVector(int length) Creates a new sparse vector of the given length that is all zero values.
SparseVector(int[] indexes, double[] values, int length, int used) Creates a new sparse vector backed by the given arrays.
SparseVector(int length, int capacity) Creates a new sparse vector of the specified length, and pre-allocates enough internal state to hold capacity non zero values.
SparseVector(java.util.List<java.lang.Double> vals) Creates a new sparse vector of the same length as vals and sets each value to the values in the list.
SparseVector(Vec toCopy) Creates a new sparse vector by copying the values from another

Method Summary

Modifier and Type	Method and Description
void	applyFunction(Function1D f) Applies the given function to each and every value in the vector.
void	applyIndexFunction(IndexFunction f) Applies the given function to each and every value in the vector.
double[]	arrayCopy() Creates a new array that contains all the values of this vector in the appropriate indices
SparseVector	clone()
void	copyTo(Vec destination) Copies the values of this Vector into another vector
double	dot(Vec v) Computes the dot product between two vectors, which is equivalent to Σ thisi*vi This method should be overloaded for a serious implementation.
boolean	equals(java.lang.Object obj, double range)
double	get(int index) Gets the value stored at a specific index in the vector
int	getLastNonZeroIndex() Returns the index of the last non-zero value, or -1 if all values are zero.
java.util.Iterator<IndexValue>	getNonZeroIterator(int start) Returns an iterator that will go over the non zero values starting from the specified index in the given vector.
int	hashCode() Provides a hashcode for Vectors.
void	increment(int index, double val) Increments the value at the given index by the given value.
boolean	isSparse() Indicates whether or not this vector is optimized for sparce computation, meaning that most values in the vector are zero - and considered implicit.
double	kurtosis() Computes the kurtosis of this vector, which is the 4th moment.
int	length() Returns the length of this vector
double	max() Returns the maximum value stored in this vector
double	median() Returns the median value in this vector
double	min() Returns the minimum value stored in this vector
void	multiply(double c, Matrix A, Vec b) If this is vector a, this this computes b = b + c aT*A
void	mutableAdd(double c) Alters this vector such that this = this + c This method should be overloaded for a serious implementation.
void	mutableAdd(double c, Vec v) Alters this vector such that this = this + c * b This method should be overloaded for a serious implementation.
void	mutableDivide(double c) Mutates this /= c This method should be overloaded for a serious implementation.
void	mutableMultiply(double c) Mutates this *= c This method should be overloaded for a serious implementation.
void	mutablePairwiseDivide(Vec b) Mutates this by dividing each value by the value in b that has the same index This method should be overloaded for a serious implementation.
void	mutablePairwiseMultiply(Vec b) Mutates this by multiplying each value by the value in b that has the same index.
int	nnz() Computes the number of non zero values in this vector
void	normalize() Mutates this vector to be normalized by the L2 norm
double	pNorm(double p) Returns the p-norm of this vector.
double	pNormDist(double p, Vec y) Returns the p-norm distance between this and another vector y.
void	set(int index, double val) Sets the value stored at a specified index in the vector
void	setLength(int length) Because sparce vectors do not have most value set, they can have their length increased, and sometimes decreased, without any effort.
double	skewness() Computes the skewness of this vector, which is the 3rd moment.
Vec	sortedCopy() Returns a copy of this array with the values moved around so that they are in sorted order
double	sum() Computes the sum of the values in this vector
java.lang.String	toString()
double	variance() Computes the variance of the values in this vector, which is Vec.standardDeviation()2
void	zeroOut() Zeroes out all values in this vector This method should be overloaded for a serious implementation.

Methods inherited from class jsat.linear.Vec

add, add, canBeMutated, copyToCol, copyToRow, countNaNs, divide, equals, getNonZeroIterator, iterator, mean, multiply, multiply, multiply, mutableAdd, mutableSubtract, mutableSubtract, mutableSubtract, normalized, pairwiseDivide, pairwiseMultiply, random, random, standardDeviation, subtract, subtract, zeros

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

SparseVector

public SparseVector(int length)

Creates a new sparse vector of the given length that is all zero values.

Parameters:

length - the length of the sparse vector

SparseVector

public SparseVector(java.util.List<java.lang.Double> vals)

Creates a new sparse vector of the same length as vals and sets each value to the values in the list.

Parameters:

vals - the list of values to create a vector from

SparseVector

public SparseVector(int length,
                    int capacity)

Creates a new sparse vector of the specified length, and pre-allocates enough internal state to hold capacity non zero values. The vector itself will start out with all zero values.

Parameters:

length - the length of the sparse vector

capacity - the number of non zero values to allocate space for

SparseVector

public SparseVector(int[] indexes,
                    double[] values,
                    int length,
                    int used)

Creates a new sparse vector backed by the given arrays. Modifying the arrays will modify the vector, and no validation will be done. This constructor should only be used in performance necessary scenarios
To make sure the input values are valid, the indexes values must be increasing and all values less than length and greater than -1 up to the first used indices.
All the values stored in values must be non zero and can not be a special value.
used must be greater than -1 and less than the length of the indexes and values arrays.
The indexes and values arrays must be the exact same length

Parameters:

indexes - the array to store the index locations in

values - the array to store the index values in

length - the length of the sparse vector

used - the number of non zero values in the vector taken from the given input arrays.

SparseVector

public SparseVector(Vec toCopy)

Creates a new sparse vector by copying the values from another

Parameters:

toCopy - the vector to copy the values of

Method Detail

length

public int length()

Description copied from class: Vec

Returns the length of this vector

Specified by:

length in class Vec

Returns:

the length of this vector

setLength

public void setLength(int length)

Because sparce vectors do not have most value set, they can have their length increased, and sometimes decreased, without any effort. The length can always be extended. The length can be reduced down to the size of the largest non zero element.

Parameters:

length - the new length of this vector

nnz

public int nnz()

Description copied from class: Vec

Computes the number of non zero values in this vector

Overrides:

nnz in class Vec

Returns:

the number of non zero values stored

increment

public void increment(int index,
                      double val)

Increments the value at the given index by the given value.

Overrides:

increment in class Vec

Parameters:

index - the index of the value to alter

val - the value to be added to the index

get

public double get(int index)

Description copied from class: Vec

Gets the value stored at a specific index in the vector

Specified by:

get in class Vec

Parameters:

index - the index to access

Returns:

the double value in the vector

set

public void set(int index,
                double val)

Description copied from class: Vec

Sets the value stored at a specified index in the vector

Specified by:

set in class Vec

Parameters:

index - the index to access

val - the value to store in the index

sortedCopy

public Vec sortedCopy()

Description copied from class: Vec

Returns a copy of this array with the values moved around so that they are in sorted order

Overrides:

sortedCopy in class Vec

Returns:

a new array in sorted order

getLastNonZeroIndex

public int getLastNonZeroIndex()

Returns the index of the last non-zero value, or -1 if all values are zero.

Returns:

the index of the last non-zero value, or -1 if all values are zero.

min

public double min()

Description copied from class: Vec

Returns the minimum value stored in this vector

Overrides:

min in class Vec

Returns:

the minimum value in this vector

max

public double max()

Description copied from class: Vec

Returns the maximum value stored in this vector

Overrides:

max in class Vec

Returns:

the maximum value in this vector

sum

public double sum()

Description copied from class: Vec

Computes the sum of the values in this vector

Overrides:

sum in class Vec

Returns:

the sum of this vector's values

variance

public double variance()

Description copied from class: Vec

Computes the variance of the values in this vector, which is Vec.standardDeviation()²

Overrides:

variance in class Vec

Returns:

the variance

median

public double median()

Description copied from class: Vec

Returns the median value in this vector

Overrides:

median in class Vec

Returns:

the median

skewness

public double skewness()

Description copied from class: Vec

Computes the skewness of this vector, which is the 3rd moment.

Overrides:

skewness in class Vec

Returns:

the skewness

kurtosis

public double kurtosis()

Description copied from class: Vec

Computes the kurtosis of this vector, which is the 4th moment.

Overrides:

kurtosis in class Vec

Returns:

the kurtosis

copyTo

public void copyTo(Vec destination)

Description copied from class: Vec

Copies the values of this Vector into another vector

Overrides:

copyTo in class Vec

Parameters:

destination - the vector to store the values in.

dot

public double dot(Vec v)

Description copied from class: Vec

Computes the dot product between two vectors, which is equivalent to
Σ this_i*v_i

This method should be overloaded for a serious implementation.

Overrides:

dot in class Vec

Parameters:

v - the other vector

Returns:

the dot product of this vector and another

toString

public java.lang.String toString()

Overrides:

toString in class Vec

multiply

public void multiply(double c,
                     Matrix A,
                     Vec b)

Description copied from class: Vec

If this is vector a, this this computes b = b + c a^T*A

Overrides:

multiply in class Vec

Parameters:

c - the constant factor to multiply by

A - the matrix to multiple by

b - the vector to mutate by adding the result to

mutableAdd

public void mutableAdd(double c)

Description copied from class: Vec

Alters this vector such that this = this + c

This method should be overloaded for a serious implementation.

Overrides:

mutableAdd in class Vec

Parameters:

c - a scalar constant to add to each value in this vector

mutableAdd

public void mutableAdd(double c,
                       Vec v)

Description copied from class: Vec

Alters this vector such that this = this + c * b

This method should be overloaded for a serious implementation.

Overrides:

mutableAdd in class Vec

Parameters:

c - a scalar constant

v - the vector to add to this

mutableMultiply

public void mutableMultiply(double c)

Description copied from class: Vec

Mutates this *= c

This method should be overloaded for a serious implementation.

Overrides:

mutableMultiply in class Vec

Parameters:

c - the constant to multiply by

mutableDivide

public void mutableDivide(double c)

Description copied from class: Vec

Mutates this /= c

This method should be overloaded for a serious implementation.

Overrides:

mutableDivide in class Vec

Parameters:

c - the constant to divide by

pNormDist

public double pNormDist(double p,
                        Vec y)

Description copied from class: Vec

Returns the p-norm distance between this and another vector y.

Overrides:

pNormDist in class Vec

Parameters:

p - the distance type. 2 is the common value

y - the other vector to compare against

Returns:

the p-norm distance

pNorm

public double pNorm(double p)

Description copied from class: Vec

Returns the p-norm of this vector.

Overrides:

pNorm in class Vec

Parameters:

p - the norm type. 2 is a common value

Returns:

the p-norm of this vector

clone

public SparseVector clone()

Specified by:

clone in class Vec

normalize

public void normalize()

Description copied from class: Vec

Mutates this vector to be normalized by the L₂ norm

Overrides:

normalize in class Vec

mutablePairwiseMultiply

public void mutablePairwiseMultiply(Vec b)

Description copied from class: Vec

Mutates this by multiplying each value by the value in b that has the same index.

This method should be overloaded for a serious implementation.

Overrides:

mutablePairwiseMultiply in class Vec

Parameters:

b - the vector to pairwise multiply by

mutablePairwiseDivide

public void mutablePairwiseDivide(Vec b)

Description copied from class: Vec

Mutates this by dividing each value by the value in b that has the same index

This method should be overloaded for a serious implementation.

Overrides:

mutablePairwiseDivide in class Vec

Parameters:

b - the vector to pairwise divide by

equals

public boolean equals(java.lang.Object obj,
                      double range)

Overrides:

equals in class Vec

arrayCopy

public double[] arrayCopy()

Description copied from class: Vec

Creates a new array that contains all the values of this vector in the appropriate indices

Overrides:

arrayCopy in class Vec

Returns:

a new array that is a copy of this vector

applyFunction

public void applyFunction(Function1D f)

Description copied from class: Vec

Applies the given function to each and every value in the vector.

This method should be overloaded for a serious implementation.

Overrides:

applyFunction in class Vec

Parameters:

f - the single variable function to apply

applyIndexFunction

public void applyIndexFunction(IndexFunction f)

Description copied from class: Vec

Applies the given function to each and every value in the vector. The function takes 2 arguments, an arbitrary value, and then an index. The index passed to the function is the index in the array that the value came from.

NOTE: Because negative values are invalid indexes. The given function should return 0.0 when given a negative index, if and only if, f(0,index) = 0 for any valid index. If f(0, index) != 0 for even one value of index, it should return any non zero value when given a negative index.

IE: f(value_i, i) = x

This method should be overloaded for a serious implementation.

Overrides:

applyIndexFunction in class Vec

Parameters:

f - the 2 dimensional index function to apply

zeroOut

public void zeroOut()

Description copied from class: Vec

Zeroes out all values in this vector

This method should be overloaded for a serious implementation.

Overrides:

zeroOut in class Vec

getNonZeroIterator

public java.util.Iterator<IndexValue> getNonZeroIterator(int start)

Description copied from class: Vec

Returns an iterator that will go over the non zero values starting from the specified index in the given vector. The iterator does not support the Iterator.remove() method.

This method should be overloaded for a serious implementation.

Overrides:

getNonZeroIterator in class Vec

Parameters:

start - the first index (inclusive) to start returning non-zero values from

Returns:

an iterator for the non zero index value pairs

hashCode

public int hashCode()

Description copied from class: Vec

Provides a hashcode for Vectors. All vector implementations should return the same result for cases when Vec.equals(java.lang.Object) returns true. Below is the code used for this class

int result = 1;

for (int i = 0; i < length(); i++)
{
double val = get(i);
if(val != 0)
{
long bits = Double.doubleToLongBits(val);
result = 31 * result + (int)(bits ^ (bits >>> 32));
result = 31 * result + i;
}
}

return 31* result + length();


Overrides:

hashCode in class Vec

Returns:

the hash code for a vector

isSparse

public boolean isSparse()

Description copied from class: Vec

Indicates whether or not this vector is optimized for sparce computation, meaning that most values in the vector are zero - and considered implicit. Only non-zero values are stored.

Specified by:

isSparse in class Vec

Returns:

true if the vector is sparce, false otherwise.