To design a sparse vector class.
You'll need to understand structs, but other than that, no
new C++ concepts are needed.
Our goal for next week is to design a sparse matrix class. Sparse matrices are often used in mathematics, engineering, and all those good science things to help compute the answers to hard problems. We use them in CS a lot, too. A "sparse" matrix can be loosely defined as one where there are enough zero entries to be worth taking advantage of them to reduce the space and/or time complexities involved in manipulating or storing them.
Breaking big problems into little ones is a central tenet of modern
software design philosophy. We'll do that by focusing this week on creating
a simpler class that represents a sparse vector. Recall that a vector
is just a one-dimensional matrix. This vector class you'll define is
special: it must be able to span as many as 2,147,483,647 elements (that's
INT_MAX for those of you keeping score at home). Since we
obviously don't want to have to store two billion elements, we had better
hope that the vector is sparse. What this means is that almost all of
the entries will be zeros. Because of this structure, using an array to
store the elements of the sparse vector is extremely wasteful; instead, we'll
use a linked list that stores only nonzero entries. This is
important: none of the entries in the linked list should be
zeroes.
Here's the interface specification for this class:
Using the exact signatures below, implement at least the
following constructors and methods. You should use reference semantics and
take advantage of const whenever possible.
SparseVector(int cols): Single-argument
constructor that takes the number of columns in this vector.
SparseVector(const SparseVector &other):
Copy constructor.
~SparseVector(): Destructor.
int getSize() const:
Total column size accessor.
int getNonZeroSize() const:
Returns the number of nonzero entries.
int getElem(int col) const:
Accessor for individual elements.
void setElem(int col, int value):
Mutator for individual elements.
The following handy operator overloads:
operator=(const SparseVector &)operator+=(const SparseVector &)operator-=(const SparseVector &)operator+(const SparseVector &) constoperator-(const SparseVector &) constoperator==(const SparseVector &) constoperator!=(const SparseVector &) constYou will have to figure out the correct return types for yourself. Also, make sure that addition and subtraction are efficient; in other words, they should take time proportional to the number of non-zero entries in the vector rather than the total size of the vector (which could be huge).
A linked list is a data structure that contains a bunch of nodes in a row where each one points to the next. You could use a struct like this to represent our non-zero columns in a list:
struct node
{
int col; // column number (between 0 and totalcols-1)
int value; // contents of this column
node *next; // next non-empty column in sorted list
node(int col, int data, node *next)
: col(col), data(data), next(next) { } // inline constructor
};
It's easy to make nodes with code like this:
node *mySecondNode = new node(someColumn, someValue, NULL);
node *myFirstNode = new node(13, -3423, mySecondNode);
As we mentioned above, you should use a linked list to represent the non-zero columns of your sparse vectors.
Compile and test this class with this test routine as follows:
% g++ -g -Wall SparseVector.cc testSparseVector.cc -o testSparseVector
Warning! If your C skills are rusty (i.e. if you don't remember how to work with linked lists, or find pointers confusing) you will find this lab extremely challenging. Even if you are comfortable with pointers and linked lists, you may find this lab taking much longer than previous labs. Try to get started early and send me email if you get stuck.