[자료구조] 희소 행렬 (Sparse Matrix)

 

Sparse Matrix는 행렬의 대부분의 요소가 0인 행렬입니다. 이와 반대로 0이 대부분이 아니라면 Dense Maxtrix라고 합니다.

 

다음과 같이 행렬에 수많은 0이 보이는 것을 알 수 있는데 이를 Sparse Matrix라고 합니다.

만약 행렬의 크기가 엄청나게 큰 상황이라면 엄청난 공간낭비가 따라올 수 밖에 없습니다.

 

Sparse Matrix의 표현은 다음과 같이 합니다.

• 행,열,값으로 특정할 수 있다.
• 행이 오름차순이 되도록하며, 행이 동일하면 열이 오름차순이 되도록한다.
• 작업이 종료되면 행의 개수, 열의 개수, 0이 아닌 값의 개수를 알도록 한다.

따라서 위의 그림을 다시 나타낸다면 다음과 같이 나타낼 수 있습니다.

a[0]에는 행의 개수, 열의 개수, 0이 아닌 값들의 총 개수가 들어갑니다.

 

 

 

다음으로 행렬의 전치에 대해서 알아보겠습니다.

다음의 방법은 dense representation 방법입니다.

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

void printMatrix(int **m, int rows, int cols) {
  int i, j;
  for(i=0; i<rows; i++) {
    for(j=0; j<cols; j++) {
      printf("%3d ", m[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}

void transpose(int **m, int rows, int cols) {
  int i, j, temp;
  for(i=0; i<rows; i++) {
    for(j=i+1; j<cols; j++) {
      // swap m[i][j] and m[j][i]
      temp = m[i][j];
      m[i][j] = m[j][i];
      m[j][i] = temp;
    }
  }
}

void main() {

  int i, j;
  int **matrix;
  matrix = malloc(6 * sizeof(*matrix));
  for(i=0; i<6; i++) {
    matrix[i] = malloc(6 * sizeof(**matrix));
    for(j=0; j<6; j++) {
      matrix[i][j] = 0;
    }
  }

  matrix[0][0] = 15;
  matrix[0][3] = 22;
  matrix[0][5] = -15;
  matrix[1][1] = 11;
  matrix[1][2] = 3;
  matrix[2][3] = -6;
  matrix[4][0] = 91;
  matrix[5][2] = 28;

  printMatrix(matrix, 6, 6);
  transpose(matrix, 6, 6);
  printMatrix(matrix, 6, 6);

  for(i=0; i<6; i++) {
    free(matrix[i]);
  }
  free(matrix);
}

 

C언어를 배웠다면 두 값을 바꾸는 swap이라는 것을 해본 적이 있을 것입니다. 여기서도 동일합니다. 

대각 원소를 제외하고 나머지 원소들에 대해서 swap을 해준다면 transpose가 완성됩니다.

void transpose(int **m, int rows, int cols) {
  int i, j, temp;
  for(i=0; i<rows; i++) {
    for(j=i+1; j<cols; j++) {
      // swap m[i][j] and m[j][i]
      temp = m[i][j];
      m[i][j] = m[j][i];
      m[j][i] = temp;
    }
  }
}

 

---

 

이보다 한 차원 높은 방법은 열의 개수를 이용하여 tramspose를 결정하여 데이터의 이동을 피하는 것입니다. 새로운 행렬에 전치된 값을 입력하는 것입니다. 

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

#define MAX_TERMS 101
typedef struct
{
  int row;
  int col;
  int value;
} term;

void printMatrix(term *);
void transpose(term *, term *);

void main()
{

  term a[MAX_TERMS], b[MAX_TERMS];

  a[0].row = 6;
  a[0].col = 6;
  a[0].value = 8; // # of rows, # or cols, # of terms
  a[1].row = 0;
  a[1].col = 0;
  a[1].value = 15;
  a[2].row = 0;
  a[2].col = 3;
  a[2].value = 22;
  a[3].row = 0;
  a[3].col = 5;
  a[3].value = -15;
  a[4].row = 1;
  a[4].col = 1;
  a[4].value = 11;
  a[5].row = 1;
  a[5].col = 2;
  a[5].value = 3;
  a[6].row = 2;
  a[6].col = 3;
  a[6].value = -6;
  a[7].row = 4;
  a[7].col = 0;
  a[7].value = 91;
  a[8].row = 5;
  a[8].col = 2;
  a[8].value = 28;

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

  printMatrix(a);
  transpose(a, b);
  printMatrix(b);
}

void printMatrix(term *m)
{

  int iter = 1, i, j;
  int rows = m[0].row;
  int cols = m[0].col;
  int num_terms = m[0].value;

  for (i = 0; i < rows; i++)
  {
    for (j = 0; j < cols; j++)
    {
      if (iter <= num_terms && m[iter].row == i && m[iter].col == j)
      {
        printf("%3d ", m[iter].value);
        iter++;
      }
      else
      {
        printf("%3d ", 0);
      }
    }
    printf("\n");
  }
  printf("\n");
}

void transpose(term *a, term *b)
{
  /* b is set to the transpose of a */
  int n, i, j, currentb;
  n = a[0].value;      /* total number of elements */
  b[0].row = a[0].col; /* rows in b = columns in a */
  b[0].col = a[0].row; /* columns in b = rows in a */
  b[0].value = n;
  if (n > 0)
  { /* non-zero matrix */
    currentb = 1;
    for (i = 0; i < a[0].col; i++)
      /* transpose by the columns in a */
      for (j = 1; j <= n; j++)
        /* find elements from the current column */
        if (a[j].col == i)
        {
          /* element is in current column, add it to b */
          b[currentb].row = a[j].col;
          b[currentb].col = a[j].row;
          b[currentb].value = a[j].value;
          currentb++;
        }
  }
}

 

여기서 살펴볼 것은 transpose 함수입니다. a[0]는 행 개수, 열 개수, 값의 개수를 가지고 있었는데, 현재 transpose를 해야하기 때문에 b[0]에 행 개수와 열 개수를 바꿔서 입력해주고 값에는 똑같은 값을 입력해줍니다.

 

이중 for문을 살펴보겠습니다. 먼저 열을 기준으로 탐색을 하기 때문에 외부 for문은 열의 개수의 오름차순으로 반복을 해줍니다. 또한 내부 반복문은 n번 반복해주는데, 여기서 n은 값의 개수입니다. 불필요한 반복을 할 필요가 없기 때문에 값의 개수를 써주는게 맞습니다.

내부 for문 속의 조건문을 살펴보겠습니다.

if (a[j].col == i)
        {
          /* element is in current column, add it to b */
          b[currentb].row = a[j].col;
          b[currentb].col = a[j].row;
          b[currentb].value = a[j].value;
          currentb++;
        }

 

그림을 함께 보면 좋을 것 같습니다.

a[0]에는 값들이 들어있는 것이 아닌 행과 열과 값의 '개수'가 들어있기 때문에 실직적인 데이터는 a[1]부터 들어있는 것을 알 수 있습니다.

a는 행을 기준으로 오름차순 행이 같다면 열을 기준으로 오름차순이라는 것을 알 수 있습니다. b도 마찬가지로 만들어주는 상황입니다.

만약 전치를 한다면 전치된 b는 a의 열을 행으로 가지며 a의 행을 열로 가질것입니다.

따라서 a의 열에서 a[j].col이 작은 값부터(0부터) b에 입력을 해나가야만 합니다. 그래서 반복문이 저렇게 쓰여진 이유이며, 현제  조건문도 위와 같이 작성한 이유입니다.

외부 반복문의 i가 0부터 커진다. 이 값이 a의 열과 같다면 이걸 b에 입력해라.

 

Q : 엥? 그러다가 b의 열(a의 행)이 순서대로 안되면 어떻게 합니까??

A : 그럴일이 없겠죠. 애초에 a가 오름차순으로 정렬되어있었기 때문에 a의 열을 기준으로 작은 값부터 확인한다고 할지라       도 그때의 그때의 행도 당연히 작은 값부터 될 확인하게 될 테니까요.

 

---

 

지금까지 두가지의 transpose 방법을 살펴보았는데 시간복잡도를 비교해보겠습니다. 첫번째 방법은 O(rows*cols)이며 두번째 방법은 O(cols*elements) = O(cols^2 * rows)입니다. 비교해 본다면 두번째 방법이 더 오래걸립니다. 그렇다면 두번째 방법을 굳이 왜 설명했을까요??

 

두 방식의 차이는 사용 시기에 있습니다. element의 개수가 얼마나 많은지에 따라 첫번째 방법이 빠를수도 두번째 방법이 빠를 수도 있습니다. 만약 element의 개수가 적으면 sparse representation를 쓰는게 좋겠지만, element의 개수가 많다면 dense representation을 쓰는게 좋습니다.

 

 

 

위 두 방법보다 더 빠르게 할 수 있는 방법이 있습니다.

void fast_transpose(term *a, term *b)
{
  /* b is set to the transpose of a */
  int row_terms[MAX_COL], starting_pos[MAX_COL];
  int i, j, num_cols = a[0].col, num_terms = a[0].value;
  b[0].row = num_cols;
  b[0].col = a[0].row;
  b[0].value = num_terms;
  if (num_terms > 0)
  { /* non-zero matrix */
    for (i = 0; i < num_cols; i++)
      row_terms[i] = 0;
    for (i = 1; i <= num_terms; i++)
      row_terms[a[i].col]++;
    starting_pos[0] = 1;
    for (i = 1; i < num_cols; i++)
      starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1];
    for (i = 1; i <= num_terms; i++)
    {
      j = starting_pos[a[i].col]++;
      b[j].row = a[i].col;
      b[j].col = a[i].row;
      b[j].value = a[i].value;
    }
  }
}

 

이 코드는 이중 반복 없이 transpose를 수행합니다.

나머지 코드들은 단순한 설정이니 반복문들을 살펴보도록 하겠습니다.

row_terms는 a의 열이 i 인 값의 개수를 입력하는 곳입니다.

예를 들어 row_terms[1] = 3이라면 현재 a의 열이 3에 해당하는 값이 3개라는 뜻입니다.

 

첫번째 반복문은 row_terms를 모두 0으로 초기화하는 과정입니다. 

 

두번째 반복문은 row_terms에 a의 열이 i 인 값의 개수를 입력하는 곳입니다.

두번째 반복문 다음에 있는 strarting_pos[0] = 1; 시작 위치를 입력하는 배열을 채우기 위해 1부터 시작한다는 것을 입력한 것입니다.

 

세번째 반복문은 row_terms에 입력된 값의 개수를 이용하여  시작 위치를 알려주는 starting_pos를 완성하는 배열입니다.예를 들어서 row_terms가 [2 1 2 2 0 1] 이었다면 a의 열이 1인 값의 개수가 2개, a의 열이 2인 값의 개수가 1개, a의 열이 3인 값의 개수가 2개, a의 열이 4인 값의 개수가 2개, ... , a의 열이 6인 값의 개수가 1개라는 뜻이었습니다. 각각의 값들을 하나의 배열 안에서 관리하려면 값들의 시작위치가 중요하겠죠, 따라서 처음 값의 시작위치를 1로 삼고, 이를 통해 starting_pos 배열을 완성하는 것입니다.

i의 starting_pos는 그럼 어떻게 될까요?? 

이전 값의 시작위치 + 이전 값의 개수 = i의 starting_pos가 되겠지요.

그렇게 starting_pos, 각 값들의 시작위치가 정해졌습니다.

 

네번째 반복문은 드디어 전치행렬 b에 행과 열과 값을 입력하는 곳입니다.

i는 1부터 천천히 증가하면서 값의 개수까지 반복을 수행합니다. 

j = starting_pos[a[i].col]++;를 통해서 열 번호가 i인 값의 시작위치를 j에 저장하고 starting_pos는 1을 증가시킵니다.

증가시키는 이유는 해당 값을 입력하는데 바로 사용할 것이고, 시작위치를 1 증가시켜 다음 값에 추후에 방문하기 위해서입니다.