[자료구조] 희소 행렬, 행렬 전치

희소 행렬(Sparse matrix)

a[m][n]

- m x n 행렬 a

• m: 행의 수
• n: 열의 수
• m x n: 원소의 수

 

- 희소 행렬

• 0이 아닌 원소 수 / 전체 원소수 << small
  → 0이 아닌 원소만 저장한다면 시간과 공간 절약

 

- 행렬에 대한 연산

• 생성(Creation)
• 전치(Transpose)
• 덧셈(Addition)
• 곱셈(Multiplication)

 

희소 행렬 표현

<행, 열, 값> 3 원소 쌍으로 식별

class MatrixTerm
{
friend class SparseMatrix;
private:
    // 행 번호, 열 번호, 값
    int row, col, value;
};

class SparseMatrix
{
private:
    // 행, 열, 0이 아닌 항의 총수, 배열크기
    int rows, cols, terms, capacity;
    MatrixTerm *smArray;
};

 

희소 행렬 예시

행 \ 열	0	1	2	3	4	5
0	15	0	0	22	0	-15
1	0	11	3	0	0	0
2	0	0	0	-6	0	0
3	0	0	0	0	0	0
4	91	0	0	0	0	0
5	0	0	28	0	0	0

 

희소 행렬과 희소 행렬의 전치행렬

smArray	행	렬	값	→ 전치 →	행	렬	값	값
0	0	0	15		0	0	0	15
1	0	3	22		1	0	4	91
2	0	5	-15		2	1	1	11
3	1	1	11		3	2	1	3
4	1	2	3		4	2	5	28
5	2	3	-6		5	3	0	22
6	4	0	91		6	3	2	-6
7	5	2	28		7	5	0	-15

원래의 행렬 각 행 i에 대하여 원소 (i, j, 값)을 가져와서 전치행렬의 원소 (j, i, 값)으로 저장

 

행렬 전치연산 프로그램

// 전치한 행렬을 반환
SparseMatrix SparseMatrix::Transpose()
{
    // terms는 b의 0이 아닌 항의 총수
    SparseMatrix b(cols, rows, terms);
    if (terms) // 행렬의 모든 값이 0이 아니라면 작업 시작
    {
        int currentB = 0;
        
        // 전치하려는 행렬의 열을 작은 순서대로 작업
        // 기존 행렬의 행은 이미 정렬되어있으므로 
        // 열을 작은 순서대로 작업하면 됨
        for (int c = 0; c < cols; c++)
        {
            // 기존 행렬을 전부 탐색
            for (int i = 0; i < terms; i++)
            {
                if (smArray[i].col == c) // 열이 c라면
                {
                    // 기존 행렬의 값들을 전치해서 저장
                    b.smArray[currentB].row = c;
                    b.smArray[currentB].col = smArray[i].row;
                    b.smArray[currentB++].value = smArray[i].value;
                }
            }
        }
    }
    return b;
}

시간 복잡도 - O(terms · cols)

 

개선된 행렬 전치연산 프로그램

프로그램 1보다 메모리를 더 사용

대신 실행시간이 더 짧음

 

- 행렬 *this의 각 열에 대한 원소 수를 구함

   → 전치 행렬 b의 각 행의 원소 수를 결정

- 이 정보에서 전치행렬 b의 각 행의 시작위치 구함

- 원래 행렬 a에 있는 원소를 하나씩 전치 행렬 b의 올바른 위치로 옮김

리턴할 전치행렬의 행	ROW_SIZE 리턴할 행렬의 행의 0이 아닌 원소 수(기존 행렬의 열)	ROW_START 리턴할 행렬의 starting position(인덱스)
[0]	2	0
[1]	1	2
[2]	2	3
[3]	2	4
[4]	0	7
[5]	1	7

 

프로그램

SparseMatrix SparseMatrix::FastTranspose()
{ // 전치한 행렬을 리턴
    SparseMatrix b(cols, rows, terms); // 리턴할 행렬
    if (terms > 0) // 행렬의 모든 값이 0이 아니라면 작업 시작
    {
        int *rowSize = new int[cols];
        int *rowStart = new int[cols];
        // rowSize[i] = b의 행 i에 있는 항 수
        fill(rowSize, rowSize + cols, 0); // 위의 표처럼 배열을 초기화
        for (i = 0; i < terms; i++)
            rowSize[smArray[i].col]++;

        // rowStart[i] = b에서 행 i의 시작 위치
        rowStart[0] = 0;
        for (i = 1; i < cols; i++)
            rowStart[i] = rowStart[i - 1] + rowSize[i - 1];

        for (i = 0; i < terms; i++)
        { // b에 기존 행렬을 전치해서 초기화
            int j = rowStart[smArray[i].col];
            b.smArray[j].row = smArray[i].col;
            b.smArray[j].col = smArray[i].row;
            b.smArray[j].value = smArray[i].value;
            rowStart[smArray[i].col]++;
        }
        delete[] rowSize;
        delete[] rowStart;
    }
    return b;
}

 

시간복잡도 - O(cols + terms)