I have faced this C++ problem:
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition how many elements need to be zero for a matrix to be considered sparse but a common criterion is that the number of non-zero elements is roughly the number of rows or columns. By contrast, if most of the elements are nonzero, then the matrix is considered dense. The number of zero-valued elements divided by the total number of elements (e.g., m × n for an m × n matrix) is sometimes referred to as the sparsity of the matrix.
Write a class for storing a sparse matrix. Your class should support matrix sizes up to 1million x 1million. Your class should be able to do any of the following:
A. Generate a random sparse matrix
B. Have the ability for an input matrix to be specified by a programmer
C. Compute the sparsity of a matrix
D. Rotate the matrix
I did research on the matter. I found this approach: A proper way to create a matrix in c++ but I a doubt this would work because the shear size requirement (1M x 1M) in the problem.
Another approach I found using maps: What is the best way to create a sparse array in C++? but it is not quite what I need and I am unsure whether the (1M x 1M) requirement is met. Not sure how to approach part B as well. Also the the map is not encapsulated in the class.
I am interested in learning how to do this. This is not a school project or anything. This was an interview question that I failed to find the answer for.
Edit: Here's my implementation. Although I need to improve on it as it crashes right now if I specify a matrix size of 1Mx1M. I need to make it store only non-zero values.
Your feedback on the implementation is appreciated.
HEADER:
#ifndef SPARSEMATRIX_H
#define SPARSEMATRIX_H
#include <map>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
class SparseMatrix
{
public:
// Default constructor
SparseMatrix(unsigned int r, unsigned int c);
// Constructor that takes a 2D vector
SparseMatrix(std::vector<std::vector<int>> matrix);
// Deconstructor
~SparseMatrix();
// Print all matrix elements on console
void printMatrix();
// Return the sparsity
float computeSparsity();
// Rotate matrix by 90 degrees clockwise
void rotate90Clockwise();
// Return the element at the specified indices
int at(unsigned int rIndex, unsigned int cIndex);
private:
// Number of rows for the matrix
unsigned int rows;
// Number of columns for the matrix
unsigned int cols;
// Holds the number of zero-value elements in matrix
unsigned int zeroCounter;
// Map to hold the matrix in key-value fashion
std::map<std::string,int> data;
};
#endif // SPARSEMATRIX_H
SOURCE:
#include "sparsematrix.h"
#define MAX_SIZE (unsigned int) 1000000
#define MIN_SIZE (unsigned int) 1
SparseMatrix::SparseMatrix( unsigned int r, unsigned int c )
{
// Acquire the size required for the matrix
rows = r;
cols = c;
zeroCounter = 0;
// Check if the desired matrix is within design limit (1Mx1M elements)
if( rows > MAX_SIZE || rows < MIN_SIZE || cols > MAX_SIZE || cols < MIN_SIZE )
throw std::out_of_range("Matrix is out of range");
// Loop to generate random values and store in map
for( unsigned int i = 0; i < rows; ++i )
{
for( unsigned int j = 0; j < cols; ++j )
{
std::string key = std::to_string(i) + "," + std::to_string(j);
// Generate random value
unsigned int value = rand() % 10;
// Keep count of zero value elements
if( value == 0 ) zeroCounter++;
// Store value in map
data[key] = value;
}
}
}
SparseMatrix::SparseMatrix(std::vector<std::vector<int> > matrix)
{
unsigned int colNum = 0;
// Compute max column length
for (unsigned int i = 0; i < matrix.size(); ++i)
{
colNum = std::max( { colNum, matrix[i].size() } );
}
// Loop to transfer the elements from vector to map
// Fill all non existent elements with zero value
for (unsigned int i = 0; i < matrix.size(); ++i)
{
for (unsigned int j = 0; j < colNum; ++j)
{
std::string key = std::to_string(i) + "," + std::to_string(j);
unsigned int value;
if( j < matrix[i].size() )
{
// Element exists
value = matrix[i][j];
}
else
{
// Element does not exist; fill with zero
value = 0;
}
// Keep count of zero value elements
if( value == 0 ) zeroCounter++;
// Store value in map
data[key] = value;
}
}
}
SparseMatrix::~SparseMatrix()
{
// Matrix deconstructor
}
void SparseMatrix::printMatrix()
{
// Print all matrix elements on console
for(auto elem : data)
{
std::cout << elem.first << " " << elem.second << std::endl;
}
std::cout << " " << std::endl;
}
float SparseMatrix::computeSparsity()
{
// Return the calculated sparsity
return ((float)zeroCounter/(rows*cols));
}
void SparseMatrix::rotate90Clockwise()
{
std::map<std::string,int> temp;
std::string oldKey;
std::string newKey;
//Transpose matrix first
for(unsigned int r = 0; r < rows; r++)
{
for(unsigned int c = r; c < cols; c++)
{
oldKey = std::to_string(r) + "," + std::to_string(c);
newKey = std::to_string(c) + "," + std::to_string(r);
temp[newKey] = data[oldKey];
if( oldKey != newKey && data.count(newKey))
temp[oldKey] = data[newKey];
}
}
// Assign the temp map to our data map
data = temp;
// Matrix is transposed now so rows and cols should be swaped
std::swap(rows, cols);
// Reverse elements of matrix on row order
for(unsigned int r = 0; r < rows; r++)
{
for(unsigned int c =0; c < cols/2; c++)
{
oldKey = std::to_string(r) + "," + std::to_string(c);
newKey = std::to_string(r) + "," + std::to_string(cols-c-1);
data[newKey] = temp[oldKey];
if( oldKey != newKey && temp.count(newKey))
data[oldKey] = temp[newKey];
}
}
}
int SparseMatrix::at(unsigned int rIndex, unsigned int cIndex)
{
// Check if the requested element is within matrix range
if( rIndex >= rows || cIndex >= cols )
throw std::out_of_range("Indices out of range");
// Construct key for the requested element
std::string key = std::to_string(rIndex) + "," + std::to_string(cIndex);
// Return element at key
return data[key];
}
