edu.princeton.cs.algs4

Class SparseVector

java.lang.Object

edu.princeton.cs.algs4.SparseVector

public class SparseVector
extends java.lang.Object

The SparseVector class represents a d-dimensional mathematical vector. Vectors are mutable: their values can be changed after they are created. It includes methods for addition, subtraction, dot product, scalar product, unit vector, and Euclidean norm.

The implementation is a symbol table of indices and values for which the vector coordinates are nonzero. This makes it efficient when most of the vector coordindates are zero.

For additional documentation, see Section 3.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. See also Vector for an immutable (dense) vector data type.

Constructor Summary

Constructors

Constructor and Description
SparseVector(int d) Initializes a d-dimensional zero vector.

Method Summary

Modifier and Type	Method and Description
int	dimension() Returns the dimension of this vector.
double	dot(double[] that) Returns the inner product of this vector with the specified array.
double	dot(SparseVector that) Returns the inner product of this vector with the specified vector.
double	get(int i) Returns the ith coordinate of this vector.
double	magnitude() Returns the magnitude of this vector.
static void	main(java.lang.String[] args) Unit tests the SparseVector data type.
int	nnz() Returns the number of nonzero entries in this vector.
double	norm() Deprecated. Replaced by magnitude().
SparseVector	plus(SparseVector that) Returns the sum of this vector and the specified vector.
void	put(int i, double value) Sets the ith coordinate of this vector to the specified value.
SparseVector	scale(double alpha) Returns the scalar-vector product of this vector with the specified scalar.
int	size() Deprecated. Replaced by dimension().
java.lang.String	toString() Returns a string representation of this vector.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SparseVector

public SparseVector(int d)

Initializes a d-dimensional zero vector.

Parameters:

d - the dimension of the vector

Method Detail

put

public void put(int i,
                double value)

Sets the ith coordinate of this vector to the specified value.

Parameters:

i - the index

value - the new value

Throws:

java.lang.IllegalArgumentException - unless i is between 0 and d-1

get

public double get(int i)

Returns the ith coordinate of this vector.

Parameters:

i - the index

Returns:

the value of the ith coordinate of this vector

Throws:

java.lang.IllegalArgumentException - unless i is between 0 and d-1

nnz

public int nnz()

Returns the number of nonzero entries in this vector.

Returns:

the number of nonzero entries in this vector

size

@Deprecated
public int size()

Deprecated. Replaced by dimension().

Returns the dimension of this vector.

Returns:

the dimension of this vector

dimension

public int dimension()

Returns the dimension of this vector.

Returns:

the dimension of this vector

dot

public double dot(SparseVector that)

Returns the inner product of this vector with the specified vector.

Parameters:

that - the other vector

Returns:

the dot product between this vector and that vector

Throws:

java.lang.IllegalArgumentException - if the lengths of the two vectors are not equal

dot

public double dot(double[] that)

Returns the inner product of this vector with the specified array.

Parameters:

that - the array

Returns:

the dot product between this vector and that array

Throws:

java.lang.IllegalArgumentException - if the dimensions of the vector and the array are not equal

magnitude

public double magnitude()

Returns the magnitude of this vector. This is also known as the L2 norm or the Euclidean norm.

Returns:

the magnitude of this vector

norm

@Deprecated
public double norm()

Deprecated. Replaced by magnitude().

Returns the Euclidean norm of this vector.

Returns:

the Euclidean norm of this vector

scale

public SparseVector scale(double alpha)

Returns the scalar-vector product of this vector with the specified scalar.

Parameters:

alpha - the scalar

Returns:

the scalar-vector product of this vector with the specified scalar

plus

public SparseVector plus(SparseVector that)

Returns the sum of this vector and the specified vector.

Parameters:

that - the vector to add to this vector

Returns:

the sum of this vector and that vector

Throws:

java.lang.IllegalArgumentException - if the dimensions of the two vectors are not equal

toString

public java.lang.String toString()

Returns a string representation of this vector.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this vector, which consists of the the vector entries, separates by commas, enclosed in parentheses

main

public static void main(java.lang.String[] args)

Unit tests the SparseVector data type.

Parameters:

args - the command-line arguments