SparseMatrix (희소 행렬)

희소행렬이란?

정확한 정의는 없지만 행렬의 원소의 대부분이 0인 행렬

-> 2D matrix로 표현시에 불필요한 메모리의 낭비가 심하다.

 

C에서 구조체를 사용하여 <row, col, val> 값으로 0이 아닌 값들만 표현이 가능

각 배열의 0번째 index의 값은 총 행, 열, 값의 수를 나타낸다.

 

#include <stdio.h>
#include<stdlib.h>

// sparse matrix 
typedef struct {
	int row;	// index of row
	int col;	// index of col
	double val;	// value
}term;

// a[i,j] -> b[j,i]
void transpose(term a[], term b[]) {
	int i, j;
	int curb;	// current index of b

	b[0].row = a[0].col;
	b[0].col = a[0].row;
	b[0].val = a[0].val;

	if (a[0].val > 0) {
		curb = 1;	
		for (i = 0; i < a[0].col; i++) {
			for (j = 1; j <= a[0].val; j++) {
				if (a[j].col == i) {	// i번째 column에 해당하는 값이 있다면..
					b[curb].row = a[j].col;
					b[curb].col = a[j].row;
					b[curb].val = a[j].val;
					curb++;
				}
			}
		}
	}
}


#define MAX_COL 100

// 메모리를 조금 더 사용해서 시간 향상
void fastTranpose(term a[], term b[]) {
	int rowTerms[MAX_COL];	// 해당 행의 총 원소개수
	int startingPos[MAX_COL];	// 해당 행의 index값을 알려주기 위함
	int i, j;
	
	b[0].row = a[0].col;
	b[0].col = a[0].row;
	b[0].val = a[0].val;	// 총 원소 수
	
	if (a[0].val > 0) {
		for (i = 0; i < a[0].col; i++) rowTerms[i] = 0;
		for (i = 1; i <= a[0].val; i++) rowTerms[a[i].col]++;
		
		startingPos[0] = 1;
		for (i = 1; i < a[0].col; i++) startingPos[i] = startingPos[i - 1] + rowTerms[i - 1];
		
		for (i = 1; i <= a[0].val; i++) {
			j = startingPos[a[i].col]++;
			b[j].row = a[i].col;
			b[j].col = a[i].row;
			b[j].val = a[i].val;
		}
	}
}