Package edu.princeton.cs.algs4

Class SparseVector

  • public class SparseVector
extends 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 coordinates 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.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

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

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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​(String[] args)
      Unit tests the SparseVector data type.
      int nnz()
      Returns the number of nonzero entries in this vector.
      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.
      String toString()
      Returns a string representation of this vector.

    • 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:
        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:
        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

      • 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:
        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:
        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

      • 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:
        IllegalArgumentException - if the dimensions of the two vectors are not equal

      • toString

        public String toString()
        Returns a string representation of this vector.
        Overrides:
        toString in class Object
        Returns:
        a string representation of this vector, which consists of the vector entries, separates by commas, enclosed in parentheses

      • main

        public static void main​(String[] args)
        Unit tests the SparseVector data type.
        Parameters:
        args - the command-line arguments