'희소행렬'에 해당되는 글 1건

  1. 2008.03.19 희소행렬과 전치행렬

희소행렬을 transpose 시키는 프로그램을 작성하였다.

transpose, fast_transpose 두 가지 방법이 있다.

#include "stdio.h"

#define  MAX_COL 50
// 희소행렬 구조체 정의 - ( 행, 열, 값 )
typedef struct
{
 int row;
 int col;
 int value;
} term;

void transpose(term a[], term b[]);
void fast_transpose(term a[], term b[]);
void init(term a[]);

/************************************************************************/
/* 함수명 : main                                                       */
/* transpose 와 fast_transpose 함수를 테스트 해본다.     */
/************************************************************************/
void main(int argc, char* argv[])
{
 term a[MAX_COL], b[MAX_COL];
 init(a);
 int i;

 for(i = 0 ; i < 9 ; i++)
 {
  printf("%d, %d, %d\n", a[i].row, a[i].col, a[i].value);
 }
 transpose(a, b);    // normal transpose
 fast_transpose(a, b);   // fast transpose
 printf("\n");
 for(i = 0 ; i < 9 ; i++)
 {
 
  printf("%d, %d, %d\n", b[i].row, b[i].col, b[i].value);
 }
}

/************************************************************************/
/* 함수명 : init                                                        */
/* sparse_matrix 를 초기화 한다.          */
/************************************************************************/
void init(term a[])
{
 a[0].row = 6;
 a[0].col = 6;
 a[0].value = 8;

 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;
 
}

/************************************************************************/
/* 함수명 : fast_transpose                                              */
/* normal transpose 함수의 연산 시간을 절약하기 위한 알고리즘이다.  */
/* 원래 행렬의 각 열에 대한 원소수를 먼저 구해서 전치 행렬에서 각 행에 */
/* 대한 원소수를 결정한다. 이 정보로부터 전치 행렬에서 각 행의 시작 위치*/
/* 를 구하고 원래 행렬에 있는 원소를 하나씩 전치 행렬의 올바른 위치로 */
/* 옮기는 것이다.              */
/* transpose 함수에서는 O( columns * elements ) 의 시간 복잡도가 나오는 */
/* 데 반하여 fast_transpose 의 시간 복잡도는 O( columns + elements ) 로 */
/* 원소의 수가 적은 경우에 훨씬 빠르다.
/************************************************************************/
void fast_transpose(term a[], term b[])
{
 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)
 {
  for(i = 0 ; i < num_cols ; i++)   // 열의 갯수만큼 반복하며 row_terms 배열을 0 으로 초기화
  {
   row_terms[i] = 0;
  }
  for(i = 1 ; i <= num_terms ; i++)  // 원소가 있는 열의 인덱스에 해당하는 row_terms 의 값을 ++
  {          // ( 열에 존재하는 원소의 개수 )
   row_terms[a[i].col]++;
   
  }

  starting_pos[0] = 1;     //  첫번째 원소는 b[1] 에 저장
 
  for(i = 1 ; i < num_cols ; i++)   // starting_pos[i] 는 전치행렬의 행 i 에 대한 시작위치를 나타낸다.
  {
   starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1]; // 바로 전 인덱스에 해당하는 row_terms 와 starting_pos
                   // 의 합이 starting_pos[i] 가 된다.
  }
  printf("\n");
  for(i = 0 ; i < num_cols ; i++)
  {
   printf("row_terms[%d] = %d\t", i, row_terms[i]);  // row_terms 출력
   printf("starting_pos[%d] = %d\n", i, starting_pos[i]); // starting_pos 출력
  }
  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                                                 */
/* a 를 transpose 하여 b 를 생성한다.         */
/************************************************************************/
void transpose(term a[], term b[])
{
 int n, i, j, currentb;
 n = a[0].value;    // 총 원소수
 b[0].row = a[0].col;  // b 의 row = a 의 col
 b[0].col = a[0].row ;  // b 의 col = a 의 row
 b[0].value = n;

 if(n > 0)
 {
  currentb = 1;
  for(i = 0 ; i < a[0].col ; i++)
  { // a 에서의 열별로 transpose
   for(j = 1; j <= n ; j++)
   { // 현재의 열로부터 원소를 찾는다.
    if(a[j].col == i)
    {
     // 현재의 열에 있는 원소를 b 에 저장한다.
     b[currentb].row = a[j].col;
     b[currentb].col = a[j].row;
     b[currentb].value = a[j].value;
     currentb++;
    }
   }
  }
 }
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요