稀疏矩陣的壓縮

稀疏矩陣的特點(diǎn)

M*N矩陣，矩陣中有效值的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于無效值的個(gè)數(shù)，并且這些數(shù)據(jù)的分布沒有規(guī)律。

例如下面的矩陣

稀疏矩陣的壓縮存儲(chǔ)

壓縮矩陣值存儲(chǔ)極少數(shù)的有效數(shù)據(jù)。使用三元組來存儲(chǔ)每一個(gè)數(shù)據(jù)，三元組數(shù)據(jù)按照矩陣中的位置，以行優(yōu)先順序依次存放。

則上述矩陣的存儲(chǔ)結(jié)構(gòu)為

三元組結(jié)構(gòu)

//三元組的定義
template<class T>
struct  Triple
{
public:
	//默認(rèn)無參構(gòu)造函數(shù)
	Triple()
	{}

	//構(gòu)造函數(shù)
	Triple(const T& d,size_t row=0,size_t col=0)
		:_value(d)
		,_row(row)
		,_col(col)
	{}
public:
	T _value;//數(shù)據(jù)域
	size_t _row;//行
	size_t _col;//列
};

稀疏矩陣的壓縮

template<class T>
class SparseMatrix
{
public:
	//無參構(gòu)造函數(shù)
	SparseMatrix()
	{}
	SparseMatrix(const T* a, size_t row, size_t col, const T& invalid);
	void Display();//打印
	SparseMatrix<T> Transport();//列轉(zhuǎn)置
	SparseMatrix<T> FastTransport();//快速轉(zhuǎn)置
	
private:
	vector<Triple<T>> _a;//三元組類型的順序表
	size_t _rowSize;//行數(shù)
	size_t _colSize;//列數(shù)
	T _invalid;//非法值
};

//矩陣的壓縮
template<class T>
SparseMatrix<T>::SparseMatrix(const T* a, size_t row, size_t col, const T& invalid)
	:_rowSize(row)
	, _colSize(col)
	, _invalid(invalid)
{
	//行遍歷
	for (size_t i = 0; i < row; i++)
	{
		//列遍歷
		for (size_t j = 0; j < col; j++)
		{
			if (a[i*col + j] != invalid)
			{
				_a.push_back(Triple<T>(a[i*col + j], i, j));
				//不能通過數(shù)組創(chuàng)建，但是可以通過數(shù)組形式訪問
			}
		}
	}
}

轉(zhuǎn)置

將原矩陣的行、列互換，也就是將[row][col]和[col][row]位置上的數(shù)據(jù)對(duì)換。

列轉(zhuǎn)置

算法思想：

采用按照被轉(zhuǎn)置矩陣三元組表A的序列（即轉(zhuǎn)置后三元組表B的行序）遞增的順序進(jìn)行轉(zhuǎn)置，并以此送入轉(zhuǎn)置后矩陣的算遠(yuǎn)足表B中，這樣一來，轉(zhuǎn)置后矩陣的三元組表B恰好是以“行序?yàn)橹餍虻摹?

實(shí)現(xiàn)代碼

//列轉(zhuǎn)置
template<class T>
SparseMatrix<T> SparseMatrix<T>::Transport()
{
	SparseMatrix<T> result;
	//行列size互換
	result._rowSize = _colSize;
	result._colSize = _rowSize;
	result._invalid = _invalid;

	//按照列掃描
	for (size_t j = 0; j < _colSize; j++)
	{
		//在三元組數(shù)組中找到相同列的元素
		for (size_t index = 0; index < _a.size(); index++)
		{
			if (_a[index]._col == j)
			{
				result._a.push_back(Triple<T>(_a[index]._value, _a[index]._col, _a[index]._row));
				//按照列優(yōu)先的順序存到壓縮數(shù)組中
			}
		}
	}
	return result;
}

算法分析：

算法的時(shí)間主要消耗在雙重循環(huán)中，其時(shí)間復(fù)雜度為O（_colSize*_a.size）。

一次定位快速轉(zhuǎn)置

算法思想：

在列轉(zhuǎn)置中算法的時(shí)間浪費(fèi)主要在雙重循環(huán)中，要改善算法的性能，必須去掉雙重循環(huán)，使得整個(gè)轉(zhuǎn)置過程通過一次循環(huán)來完成。

為了能使得被轉(zhuǎn)置的三元組表A中元素一次定位到三元組表B中，需要預(yù)先計(jì)算一下數(shù)據(jù)：

1）rowCounts,三元組表A中每一列有效值的個(gè)數(shù)，即轉(zhuǎn)置后矩陣三元組表B中每一行有效值的個(gè)數(shù)。

2）rowStart,三元組表B中每一行有效值的起始位置。

rowStart[col]=rowStart[col-1]+rowCounts[col-1]

上述矩陣的兩個(gè)數(shù)組為：

代碼實(shí)現(xiàn)：

//快速轉(zhuǎn)置
template<class T>
SparseMatrix<T> SparseMatrix<T>::FastTransport()
{
	assert(_a.size() < 0);
	SparseMatrix<T> result;
	//行列size互換
	result._rowSize = _colSize;
	result._colSize = _rowSize;
	result._invalid = _invalid;

	//建立rowCounts和rowStart
	int* rowCounts = new int[_colSize];
	int* rowStart = new int[_colSize];
	memset(rowCounts, 0, sizeof(int)*_colSize);//初始化為0
	memset(rowStart, 0, sizeof(int)*_colSize);//初始化為0

	result._a.resize(_a.size());//復(fù)制順序表_a，容量相同，但是數(shù)據(jù)不同。
	//初始化
	for (size_t i = 0; i < _colSize; i++)
	{
		rowCounts[_a[i]._col]++;
	}
	rowStart[0] = 0;
	for (size_t i = 1; i < _colSize; i++)
	{
		rowStart[i] = rowCounts[i - 1] + rowStart[i - 1];
	}

	//快速轉(zhuǎn)置
	size_t index = 0;
	Triple<T> tmp;
	while (index < _a.size())
	{
		int row = _a[index]._col;//行數(shù)
		int rowIndex = rowStart[row];//當(dāng)前行的起始位置

									 //交換行和列
		tmp._value = _a[index]._value;
		tmp._row = _a[index]._col;
		tmp._col = _a[index]._row;

		result._a[rowIndex] = tmp;
		rowStart[row]++;
		index++;
	}
	delete[] rowCounts;
	delete[] rowStart;
	return result;

}

算法分析：

一次定位快速轉(zhuǎn)置算法時(shí)間主要浪費(fèi)在3個(gè)并列的循環(huán)中，分別執(zhí)行了_colSize,_col_Size,_a.size()次，總的時(shí)間復(fù)雜度為O(_colSize+_a.size())。遠(yuǎn)遠(yuǎn)小于O（_colSize*_a.size）。