C++ Online Compiler
Example: Fast Sparse Matrix Transpose in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Fast Sparse Matrix Transpose #include <iostream> #include <vector> #include <string> // For std::string // Structure to represent a non-zero element in the sparse matrix struct Term { int row; int col; int value; }; // Structure to represent the sparse matrix itself struct SparseMatrix { int numRows; int numCols; int numTerms; // Number of non-zero elements std::vector<Term> terms; }; // Function to print a sparse matrix void printSparseMatrix(const SparseMatrix& matrix, const std::string& title) { std::cout << title << ":\n"; std::cout << "Rows: " << matrix.numRows << ", Cols: " << matrix.numCols << ", Non-zero terms: " << matrix.numTerms << "\n"; std::cout << "Row\tCol\tValue\n"; for (const auto& term : matrix.terms) { std::cout << term.row << "\t" << term.col << "\t" << term.value << "\n"; } std::cout << "\n"; } // Function to perform fast transpose SparseMatrix fastTranspose(const SparseMatrix& original) { SparseMatrix transposed; transposed.numRows = original.numCols; transposed.numCols = original.numRows; transposed.numTerms = original.numTerms; transposed.terms.resize(original.numTerms); if (original.numTerms == 0) { return transposed; } // Step 1: Create 'colCount' array to store the number of non-zero terms in each column std::vector<int> colCount(original.numCols, 0); for (int i = 0; i < original.numTerms; ++i) { colCount[original.terms[i].col]++; } // Step 2: Create 'startingPos' array to store the starting index for each column in the transposed matrix std::vector<int> startingPos(original.numCols, 0); // The first column's starting position in the transposed matrix is 0 // For subsequent columns, the starting position is the sum of previous colCounts for (int i = 1; i < original.numCols; ++i) { startingPos[i] = startingPos[i-1] + colCount[i-1]; } // Step 3: Populate the transposed matrix for (int i = 0; i < original.numTerms; ++i) { int originalCol = original.terms[i].col; int targetIndex = startingPos[originalCol]; // Get the correct index for this term in transposed transposed.terms[targetIndex].row = original.terms[i].col; // New row is old column transposed.terms[targetIndex].col = original.terms[i].row; // New col is old row transposed.terms[targetIndex].value = original.terms[i].value; startingPos[originalCol]++; // Increment starting position for the next term from this column } return transposed; } int main() { // Step 1: Define an example sparse matrix SparseMatrix originalMatrix = { 4, // numRows 5, // numCols 6, // numTerms { {0, 4, 8}, {2, 2, 3}, {3, 0, 1}, {0, 0, 10}, {1, 1, 5}, {3, 2, 7} } }; // Step 2: Print the original matrix representation printSparseMatrix(originalMatrix, "Original Sparse Matrix"); // Step 3: Perform fast transpose SparseMatrix transposedMatrix = fastTranspose(originalMatrix); // Step 4: Print the transposed matrix representation printSparseMatrix(transposedMatrix, "Transposed Sparse Matrix (Fast Transpose)"); return 0; }
Output
Clear
ADVERTISEMENTS