package jsat.linear;
import static java.lang.Math.*;
import java.util.*;
import jsat.math.Function1D;
import jsat.math.IndexFunction;
import jsat.utils.DoubleList;
import jsat.utils.IndexTable;
/**
* 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 {@link DenseVector}. The more values that are zero in the vector,
* the better its performance will be.
*
* @author Edward Raff
*/
public class SparseVector extends Vec
{
private static final long serialVersionUID = 8591745505666264662L;
/**
* Length of the vector
*/
private int length;
/**
* number of indices used in this vector
*/
protected int used;
/**
* The mapping to true index values
*/
protected int[] indexes;
/**
* The Corresponding values for each index
*/
protected double[] values;
/**
* Creates a new sparse vector of the given length that is all zero values.
*
* @param length the length of the sparse vector
*/
public SparseVector(int length)
{
this(length, 10);
}
/**
* Creates a new sparse vector of the same length as {@code vals} and sets
* each value to the values in the list.
*
* @param vals the list of values to create a vector from
*/
public SparseVector(List vals)
{
this(vals.size());
int z = 0;
for(int i = 0; i < vals.size(); i++)
if(vals.get(i) != 0)
{
if(z >= indexes.length)
{
indexes = Arrays.copyOf(indexes, indexes.length*3/2);
values = Arrays.copyOf(values, values.length*3/2);
}
indexes[z] = i;
values[z++] = vals.get(i);
}
}
/**
* Creates a new sparse vector of the specified length, and pre-allocates
* enough internal state to hold {@code capacity} non zero values. The
* vector itself will start out with all zero values.
*
* @param length the length of the sparse vector
* @param capacity the number of non zero values to allocate space for
*/
public SparseVector(int length, int capacity)
{
this(new int[capacity], new double[capacity], length, 0);
}
/**
* 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 {@code indexes } values must
* be increasing and all values less than {@code length} and greater than
* {@code -1} up to the first {@code used} indices.
* All the values stored in {@code values} must be non zero and can not be a
* special value.
* {@code used} must be greater than -1 and less than the length of the
* {@code indexes} and {@code values} arrays.
* The {@code indexes} and {@code values} arrays must be the exact same
* length
*
* @param indexes the array to store the index locations in
* @param values the array to store the index values in
* @param length the length of the sparse vector
* @param used the number of non zero values in the vector taken from the
* given input arrays.
*/
public SparseVector(int[] indexes, double[] values, int length, int used)
{
if(values.length != indexes.length)
throw new IllegalArgumentException("Index and Value arrays must have the same length, instead index was " + indexes.length + " and values was " + values.length);
if(used < 0 || used > length || used > values.length)
throw new IllegalArgumentException("Bad used value. Used must be in the range of 0 and min of values length (" + values.length + ") and array length (" + length + "), instead was given " + used);
if(length <= 0)
throw new IllegalArgumentException("Length of sparse vector must be positive, not " + length);
this.used = used;
this.length = length;
this.indexes = indexes;
this.values = values;
}
/**
* Creates a new sparse vector by copying the values from another
* @param toCopy the vector to copy the values of
*/
public SparseVector(Vec toCopy)
{
this(toCopy.length(), toCopy.nnz());
for(IndexValue iv : toCopy)
{
indexes[used] = iv.getIndex();
values[used++] = iv.getValue();
}
}
@Override
public int length()
{
return 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.
*
* @param length the new length of this vector
*/
public void setLength(int length)
{
if(used > 0 && length < indexes[used-1])
throw new RuntimeException("Can not set the length to a value less then an index already in use");
this.length = length;
}
@Override
public int nnz()
{
return used;
}
/**
* Removes a non zero value by shifting everything to the right over by one
* @param nzIndex the index to remove (setting it to zero)
*/
private void removeNonZero(int nzIndex)
{
for(int i = nzIndex+1; i < used; i++)
{
values[i-1] = values[i];
indexes[i-1] = indexes[i];
}
used--;
}
/**
* Increments the value at the given index by the given value.
* @param index the index of the value to alter
* @param val the value to be added to the index
*/
@Override
public void increment(int index, double val)
{
if (index > length - 1 || index < 0)
throw new IndexOutOfBoundsException("Can not access an index larger then the vector or a negative index");
if(val == 0)//donst want to insert a zero, and a zero changes nothing
return;
int location = Arrays.binarySearch(indexes, 0, used, index);
if(location < 0)
insertValue(location, index, val);
else
{
values[location]+=val;
if(values[location] == 0.0)
removeNonZero(location);
}
}
@Override
public double get(int index)
{
if (index > length - 1 || index < 0)
throw new ArithmeticException("Can not access an index larger then the vector or a negative index");
int location = Arrays.binarySearch(indexes, 0, used, index);
if (location < 0)
return 0.0;
else
return values[location];
}
@Override
public void set(int index, double val)
{
if(index > length()-1 || index < 0)
throw new IndexOutOfBoundsException(index + " does not fit in [0," + length + ")");
int insertLocation = Arrays.binarySearch(indexes, 0, used, index);
if(insertLocation >= 0)
{
if(val != 0)//set it
values[insertLocation] = val;
else//shift used count and everyone over
{
removeNonZero(insertLocation);
}
}
else if(val != 0)//dont insert 0s, that is stupid
insertValue(insertLocation, index, val);
}
/**
* Takes the negative insert location value returned by {@link Arrays#binarySearch(int[], int, int, int) }
* and adjust the vector to add the given value into this location. Should only be called with negative
* input returned by said method. Should never be called for an index that in fact does already exist
* in this sparce vector.
*
* @param insertLocation the negative insertion index such that -(insertLocation+1) is the address that the value should have
* @param index the index that is being added
* @param val the value that is being added for the given index
*/
private void insertValue(int insertLocation, int index, double val)
{
insertLocation = -(insertLocation+1);//Convert from negative value to the location is should be placed, see JavaDoc of binarySearch
if(used == indexes.length)//Full, expand
{
int newIndexesSize = Math.max(Math.min(indexes.length*2, Integer.MAX_VALUE), 8);
indexes = Arrays.copyOf(indexes, newIndexesSize);
values = Arrays.copyOf(values, newIndexesSize);
}
if(insertLocation < used)//Instead of moving indexes over manualy, set it up to use a native System call to move things out of the way
{
System.arraycopy(indexes, insertLocation, indexes, insertLocation+1, used-insertLocation);
System.arraycopy(values, insertLocation, values, insertLocation+1, used-insertLocation);
}
indexes[insertLocation] = index;
values[insertLocation] = val;
used++;
}
@Override
public Vec sortedCopy()
{
IndexTable it = new IndexTable(DoubleList.unmodifiableView(values, used));
double[] newValues = new double[used];
int[] newIndecies = new int[used];
int lessThanZero = 0;
for(int i = 0; i < used; i++)
{
int origIndex = it.index(i);
newValues[i] = values[origIndex];
if(newValues[i] < 0)
lessThanZero++;
newIndecies[i] = i;
}
//all < 0 values are right, now correct > 0 values
for(int i = lessThanZero; i < used; i++)
newIndecies[i] = length-(used-lessThanZero)+(i-lessThanZero);
SparseVector sv = new SparseVector(length);
sv.used = this.used;
sv.values = newValues;
sv.indexes = newIndecies;
return sv;
}
/**
* Returns the index of the last non-zero value, or -1 if all values are zero.
* @return the index of the last non-zero value, or -1 if all values are zero.
*/
public int getLastNonZeroIndex()
{
if(used == 0)
return -1;
return indexes[used-1];
}
@Override
public double min()
{
double result = 0;
for(int i = 0; i < used; i++)
result = Math.min(result, values[i]);
return result;
}
@Override
public double max()
{
double result = 0;
for(int i = 0; i < used; i++)
result = Math.max(result, values[i]);
return result;
}
@Override
public double sum()
{
/*
* Uses Kahan summation algorithm, which is more accurate then
* naively summing the values in floating point. Though it
* does not guarenty the best possible accuracy
*
* See: http://en.wikipedia.org/wiki/Kahan_summation_algorithm
*/
double sum = 0;
double c = 0;
for(int i = 0; i < used; i++)
{
double d = values[i];
double y = d - c;
double t = sum+y;
c = (t - sum) - y;
sum = t;
}
return sum;
}
@Override
public double variance()
{
double mu = mean();
double tmp = 0;
double N = length();
for(int i = 0; i < used; i++)
tmp += Math.pow(values[i]-mu, 2);
//Now add all the zeros into it
tmp += (length()-used) * Math.pow(0-mu, 2);
tmp /= N;
return tmp;
}
@Override
public double median()
{
if(used < length/2)//more than half zeros, so 0 must be the median
return 0.0;
else
return super.median();
}
@Override
public double skewness()
{
double mean = mean();
double numer = 0, denom = 0;
for(int i = 0; i < used; i++)
{
numer += pow(values[i]-mean, 3);
denom += pow(values[i]-mean, 2);
}
//All the zero's we arent storing
numer += pow(-mean, 3)*(length-used);
denom += pow(-mean, 2)*(length-used);
numer /= length;
denom /= length;
double s1 = numer / (pow(denom, 3.0/2.0) );
if(length >= 3)//We can use the bias corrected formula
return sqrt(length*(length-1))/(length-2)*s1;
return s1;
}
@Override
public double kurtosis()
{
double mean = mean();
double tmp = 0;
double var = 0;
for(int i = 0; i < used; i++)
{
tmp += pow(values[i]-mean, 4);
var += pow(values[i]-mean, 2);
}
//All the zero's we arent storing
tmp += pow(-mean, 4)*(length-used);
var += pow(-mean, 2)*(length-used);
tmp /= length;
var /= length;
return tmp / pow(var, 2) - 3;
}
@Override
public void copyTo(Vec destination)
{
if(destination instanceof SparseVector)
{
SparseVector other = (SparseVector) destination;
if(other.indexes.length < this.used)
{
other.indexes = Arrays.copyOf(this.indexes, this.used);
other.values = Arrays.copyOf(this.values, this.used);
other.used = this.used;
}
else
{
other.used = this.used;
System.arraycopy(this.indexes, 0, other.indexes, 0, this.used);
System.arraycopy(this.values, 0, other.values, 0, this.used);
}
}
else
super.copyTo(destination);
}
@Override
public double dot(Vec v)
{
double dot = 0;
if(v instanceof SparseVector)
{
SparseVector b = (SparseVector) v;
int p1 = 0, p2 = 0;
while (p1 < used && p2 < b.used)
{
int a1 = indexes[p1], a2 = b.indexes[p2];
if (a1 == a2)
dot += values[p1++] * b.values[p2++];
else if (a1 > a2)
p2++;
else
p1++;
}
}
else if(v.isSparse())
return super.dot(v);
else// it is dense
for (int i = 0; i < used; i++)
dot += values[i] * v.get(indexes[i]);
return dot;
}
@Override
public String toString()
{
StringBuilder sb = new StringBuilder("[");
int p = 0;
for(int i = 0; i < length(); i++)
{
if(i != 0)
sb.append(", ");
if(p < used && indexes[p] == i)
sb.append(values[p++]);
else
sb.append("0.0");
}
sb.append("]");
return sb.toString();
}
@Override
public void multiply(double c, Matrix A, Vec b)
{
if(this.length() != A.rows())
throw new ArithmeticException("Vector x Matrix dimensions do not agree");
else if(b.length() != A.cols())
throw new ArithmeticException("Destination vector is not the right size");
for(int i = 0; i < used; i++)
{
double val = c*this.values[i];
int index = this.indexes[i];
for(int j = 0; j < A.cols(); j++)
b.increment(j, val*A.get(index, j));
}
}
@Override
public void mutableAdd(double c)
{
if(c == 0.0)
return;
/* This NOT the most efficient way to implement this.
* But adding a constant to every value in a sparce
* vector defeats its purpos.
*/
for(int i = 0; i < length(); i++)
this.set(i, get(i) + c);
}
@Override
public void mutableAdd(double c, Vec v)
{
if(c == 0.0)
return;
if(v instanceof SparseVector)
{
SparseVector b = (SparseVector) v;
int p1 = 0, p2 = 0;
while (p1 < used && p2 < b.used)
{
int a1 = indexes[p1], a2 = b.indexes[p2];
if (a1 == a2)
{
values[p1] += c*b.values[p2];
p1++;
p2++;
}
else if (a1 > a2)
{
//0 + some value is that value, set it
this.set(a2, c*b.values[p2]);
/*
* p2 must be increment becase were moving to the next value
*
* p1 must be be incremented becase a2 was less thenn the current index.
* So the inseration occured before p1, so for indexes[p1] to == a1,
* p1 must be incremented
*
*/
p1++;
p2++;
}
else//a1 < a2, thats adding 0 to this vector, nothing to do.
{
p1++;
}
}
//One of them is now empty.
//If b is not empty, we must add b to this. If b is empty, we would be adding zeros to this [so we do nothing]
while(p2 < b.used)
this.set(b.indexes[p2], c*b.values[p2++]);//TODO Can be done more efficently
}
else if(v.isSparse())
{
if(v.nnz() == 0)
return;
int p1 = 0;
Iterator iter = v.getNonZeroIterator();
IndexValue iv = iter.next();
while(p1 < used && iv != null)
{
int a1 = indexes[p1];
int a2 = iv.getIndex();
if(a1 == a2)
{
values[p1++] += c*iv.getValue();
if(iter.hasNext())
iv = iter.next();
else
break;
}
else if(a1 > a2)
{
this.set(a2, c*iv.getValue());
p1++;
if(iter.hasNext())
iv = iter.next();
else
break;
}
else
p1++;
}
}
else
{
//Else it is dense
for(int i = 0; i < length(); i++)
this.set(i, this.get(i) + c*v.get(i));
}
}
@Override
public void mutableMultiply(double c)
{
if(c == 0.0)
{
zeroOut();
return;
}
for(int i = 0; i < used; i++)
values[i] *= c;
}
@Override
public void mutableDivide(double c)
{
if(c == 0 && used != length)
throw new ArithmeticException("Division by zero would occur");
for(int i = 0; i < used; i++)
values[i] /= c;
}
@Override
public double pNormDist(double p, Vec y)
{
if(this.length() != y.length())
throw new ArithmeticException("Vectors must be of the same length");
double norm = 0;
if (y instanceof SparseVector)
{
int p1 = 0, p2 = 0;
SparseVector b = (SparseVector) y;
while (p1 < this.used && p2 < b.used)
{
int a1 = indexes[p1], a2 = b.indexes[p2];
if (a1 == a2)
{
norm += Math.pow(Math.abs(this.values[p1] - b.values[p2]), p);
p1++;
p2++;
}
else if (a1 > a2)
norm += Math.pow(Math.abs(b.values[p2++]), p);
else//a1 < a2, this vec has a value, other does not
norm += Math.pow(Math.abs(this.values[p1++]), p);
}
//One of them is now empty.
//So just sum up the rest of the elements
while(p1 < this.used)
norm += Math.pow(Math.abs(this.values[p1++]), p);
while(p2 < b.used)
norm += Math.pow(Math.abs(b.values[p2++]), p);
}
else
{
int z = 0;
for (int i = 0; i < length(); i++)
{
//Move through until we hit our next non zero element
while (z < used && indexes[z] > i)
norm += Math.pow(Math.abs(-y.get(i++)), p);
//We made it! (or are at the end). Is our non zero value the same?
if (z < used && indexes[z] == i)
norm += Math.pow(Math.abs(values[z++] - y.get(i)), p);
else//either we used a non zero of this in the loop or we are out of them
norm += Math.pow(Math.abs(-y.get(i)), p);
}
}
return Math.pow(norm, 1.0/p);
}
@Override
public double pNorm(double p)
{
if (p <= 0)
throw new IllegalArgumentException("norm must be a positive value, not " + p);
double result = 0;
if (p == 1)
{
for (int i = 0; i < used; i++)
result += abs(values[i]);
}
else if (p == 2)
{
for (int i = 0; i < used; i++)
result += values[i] * values[i];
result = Math.sqrt(result);
}
else if (Double.isInfinite(p))
{
for (int i = 0; i < used; i++)
result = Math.max(result, abs(values[i]));
}
else
{
for (int i = 0; i < used; i++)
result += Math.pow(Math.abs(values[i]), p);
result = pow(result, 1 / p);
}
return result;
}
@Override
public SparseVector clone()
{
SparseVector copy = new SparseVector(length, Math.max(used, 10));
System.arraycopy(this.values, 0, copy.values, 0, this.used);
System.arraycopy(this.indexes, 0, copy.indexes, 0, this.used);
copy.used = this.used;
return copy;
}
@Override
public void normalize()
{
double sum = 0;
for(int i = 0; i < used; i++)
sum += values[i]*values[i];
sum = Math.sqrt(sum);
mutableDivide(Math.max(sum, 1e-10));
}
@Override
public void mutablePairwiseMultiply(Vec b)
{
if(this.length() != b.length())
throw new ArithmeticException("Vectors must have the same length");
for(int i = 0; i < used; i++)
values[i] *= b.get(indexes[i]);//zeros stay zero
}
@Override
public void mutablePairwiseDivide(Vec b)
{
if(this.length() != b.length())
throw new ArithmeticException("Vectors must have the same length");
for (int i = 0; i < used; i++)
values[i] /= b.get(indexes[i]);//zeros stay zero
}
@Override
public boolean equals(Object obj, double range)
{
if(!(obj instanceof Vec))
return false;
Vec otherVec = (Vec) obj;
range = Math.abs(range);
if(this.length() != otherVec.length())
return false;
int z = 0;
for (int i = 0; i < length(); i++)
{
//Move through until we hit the next null element, comparing the other vec to zero
while (z < used && indexes[z] > i)
if (Math.abs(otherVec.get(i++)) > range)//We are zero!
return false;
//We made it! (or are at the end). Is our non zero value the same?
if (z < used && indexes[z] == i)
if (Math.abs(values[z++] - otherVec.get(i)) > range)
if (Double.isNaN(values[z++]) && Double.isNaN(otherVec.get(i)))//NaN != NaN is always true, so check special
return true;
else
return false;
}
return true;
}
@Override
public double[] arrayCopy()
{
double[] array = new double[length()];
for(int i = 0; i < used; i++)
array[indexes[i]] = values[i];
return array;
}
@Override
public void applyFunction(Function1D f)
{
if(f.f(0.0) != 0.0)
super.applyFunction(f);
else//Then we only need to apply it to the non zero values!
{
for(int i = 0; i < used; i++)
values[i] = f.f(values[i]);
}
}
@Override
public void applyIndexFunction(IndexFunction f)
{
if(f.f(0.0, -1) != 0.0)
super.applyIndexFunction(f);
else//Then we only need to apply it to the non zero values!
{
/*
* The indexFunction may turn a value to zero, if so, we need to
* shift everything over and skip based on how many zeros have been
* created
*/
int skip = 0;
for(int i = 0; i < used; i++)
{
indexes[i-skip] = indexes[i];
values[i-skip] = f.indexFunc(values[i], i);
if(values[i-skip] == 0.0)
skip++;
}
used -= skip;
}
}
@Override
public void zeroOut()
{
this.used = 0;
}
@Override
public Iterator getNonZeroIterator(final int start)
{
if(used <= 0)
return Collections.EMPTY_LIST.iterator();
final int startPos;
if(start <= indexes[0])
startPos = 0;
else
{
int tmpIndx = Arrays.binarySearch(indexes, 0, used, start);
if(tmpIndx >= 0)
startPos = tmpIndx;
else
startPos = -(tmpIndx)-1;
}
Iterator itor = new Iterator()
{
int curUsedPos = startPos;
IndexValue indexValue = new IndexValue(-1, Double.NaN);
@Override
public boolean hasNext()
{
return curUsedPos < used;
}
@Override
public IndexValue next()
{
indexValue.setIndex(indexes[curUsedPos]);
indexValue.setValue(values[curUsedPos++]);
return indexValue;
}
@Override
public void remove()
{
throw new UnsupportedOperationException("Not supported yet.");
}
};
return itor;
}
@Override
public int hashCode()
{
int result = 1;
for (int i = 0; i < used; i++)
{
long bits = Double.doubleToLongBits(values[i]);
result = 31 * result + (int)(bits ^ (bits >>> 32));
result = 31 * result + indexes[i];
}
return 31* result + length;
}
@Override
public boolean isSparse()
{
return true;
}
}
Ads help maintain this website.