[C로 쓴 자료구조] 희소 행렬 Fast Transpose

b 행렬과 같이 value에 0이 많이 포함되는 행렬을 희소 행렬이라고 한다.

1000*1000 행렬에서 그 값의 대부분이 0일 때, 0을 저장하기 위해 1000*1000의 메모리를 사용하려 한다면 매우 큰 메모리 낭비이므로  <row, col, value> 구조의  구조체를 사용하여 값이 0인 좌표는 과감하게 버리고 유용한 값만 메모리에 저장한다.

 

 

 

 

이렇게 저장한 희소 행렬은 전치를 어떻게 할까?

보통 행렬은 전치를 하려면 row와 col값만 바꿔주면 된다.

하지만 위처럼 구조체를 활용하여 0의 값을 버린 행렬은 전치하기가 쉽지 않다.

 

row와 col만 바꿔준다면 그 순서가 정렬 되어 있지 않을 것이고, row와 col을 바꾼 뒤 정렬까지 하려면 그 시간 복잡도가 O(N^3)이므로 매우 비효율 적이다.

 

따라서 다음과 같은 알고리즘을 적용해 보자.

 

먼저 row_term 배열을 만든 후

전치시킬 a행렬의 col 좌표가 몇번 나왔는지 row_term 배열에 저장한다.

예를 들어 a행렬의 col 0인 좌표가 2개 있다면 row_term [0]=2가 되도록 하는 것이다.

 

그다음 b행렬의 row 위치 시작점을 저장할 starting_pos 배열을 만든다.

 

위에서 만든 row_term 배열을 사용하여 자동적으로 starting_pos를 계산할 수 있다.

그 식은 다음과 같다.

starting_pos[i] = starting_pos[i-1] + row_term[i-1]

 

위 starting_pos를 사용하여 a전치 행렬인 b행렬을 손쉽게 만들 수 있다.

 

 

 

c언어로 쓴 code

 

#include <stdio.h>

typedef struct { //행렬 원소를 저장하기 위한 구조체 term 정의
  int row;
  int col;
  int value;
} term;

void fast_transpose(term a[], term b[]) {
  int MAX_COL = a[0].value + 1; //행렬의 갯수
  int row_term[a[0].col], starting_pos[a[0].col];

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

  for (int i = 0; i < a[0].col; i++) {
    row_term[i] = 0;
    starting_pos[i] = 0;
  }
  starting_pos[0] = 1;

  for (int i = 1; i < MAX_COL; i++) {
    row_term[a[i].col]++;
  }

  for (int i = 1; i < a[0].col; i++) {
    starting_pos[i] = starting_pos[i - 1] + row_term[i - 1];
  }

  for (int i = 1; i < MAX_COL; i++) {
    b[starting_pos[a[i].col]].row = a[i].col;
    b[starting_pos[a[i].col]].col = a[i].row;
    b[starting_pos[a[i].col]].value = a[i].value;
    starting_pos[a[i].col]++;
  }
}

int main(void) {

  term a[9] = {{6, 6, 8}, {0, 0, 15}, {0, 3, 22}, {0, 5, -15}, {1, 1, 11},
               {1, 2, 3}, {2, 3, -6}, {4, 0, 91}, {5, 2, 28}};
  term b[9];

  fast_transpose(a, b);

  for (int i = 1; i < 9; i++) {
    printf("행: %d, 열: %d, 값: %d\n", b[i].row, b[i].col, b[i].value);
  }
  return 0;
}

 

위와 같은 알고리즘을 사용한 경우 시간 복잡도는 O(rows*cols) 이므로 O(N^3)보다 매우 효율적이다.