희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬

Presentation on theme: "희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬"— Presentation transcript:

1 희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬
no. of total elements no. of non-zero elements << small col0 col1 col2 row0 -27 3 4 row1 6 82 -2 row2 109 -64 11 row3 12 8 9 row4 48 27 47 col0 col1 col2 col3 col4 col5 row0 15 22 -15 row1 11 3 row2 -6 row3 row4 91 row5 28

2 희소 행렬 희소 행렬의 추상데이터 타입 ADT sparseMatrix
object: 3원소 쌍 <행, 열, 값>의 집합이다. 여기서, 행과 열은 정수이고 이 조합은 유일하며, 값은 item집합의 원소이다. functions : 모든 a, b∈sparseMatrix, x∈item, i, j, maxCol, maxRow∈index에 sparseMatrix Create(maxRow, maxCol) ::= return maxItems까지 저장할 수 있는 sparseMatrix 여기서 최대 행의 수는 maxRow이고 최대 열의 수는 maxCol이라 할때 maItems = maxRowmaxCol이다. sparseMatrix Transpose(a) ::= return 모든 3원소 쌍의 행과 열의 값을 교환하여 얻은 행렬 sparseMatrix Add(a,b) ::= if a와 b의 차원이 같으면 return 대응 항들 즉, 똑같은 행과 열의 값을 가진 항들을 더해서 만들어진 행렬 else return 에러

3 희소 행렬 희소 행렬의 표현 3원소쌍<행(row), 열(col), 쌍(value)>으로 표현
전치연산을 효율적으로 표현하기 위해 오름차순으로 조직 열 인덱스가 오름차순으로 정렬되도록 조직 연산 종료를 보장하기 위해 행과 열의 수와 행렬 내에 있는 0이 아닌 항의 수를 알아야 함 sparseMatrix Multiply(a,b) ::= if a의 열의 수와 b의 행의 수가 같으면 return 다음 공식에 따라 a와 b를 곱해서 생성된 행렬 d : d(i, j) = ∑(a[i][k] b[k][j]) 여기서 d(i, j)는 (i, j)번째 원소이다. else return 에러

4 행렬의 전치(Matrix Transpose)
원소 <i, j, 값>을 가져와서 전치 행렬의 원소 <j, i, 값>으로 저장 ex) (0, 0, 15) 는 (0, 0, 15) (0, 3, 22) 는 (3, 0, 22) (0, 5, -15) 는 (5, 0, -15) 행 열 값 a[0] 6 8 a[1] 15 a[2] 3 22 a[3] 5 -15 a[4] 1 11 a[5] 2 a[6] -6 a[7] 4 91 a[8] 28 행 열 값 b[0] 6 8 b[1] 15 b[2] 4 91 b[3] 1 11 b[4] 2 3 b[5] 5 28 b[6] 22 b[7] -6 b[8] -15

5 행렬의 전치 희소 행렬의 전치 for (j = 0; j < colums; j++)
for(i = 0; i < rows; i++) b[j][i] = a[i][j]; void transpose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int n, i, j, currentb; n = a[0].value; /* 총 원소 수 */ b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */ b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */ b[0].value = n; if (n>0) { /* 0이 아닌 행렬 */ currentb = 1; for (i=0; i=a[0].col; i++) /* a에서 열별로 전치 */ 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++; } }

6 행렬의 전치(3/3) 희소 행렬의 빠른전치 void fasttranspose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int rowTerms[MAX_COL], startingPose[MAX_COL]; int i, j, numCol = a[0].col, numTerms = a[0].value; b[0].row = numCols; b[0].col = a[0].row; b[0].value = numTerms; if (numTerms >0) { /* 0이 아닌 행렬 */ for(i=0; i<numCols; i++) rowTerms[i] = 0; for(i=1; i<=numTerms; i++) rowTerms[a[i].col]++; startingPos[0]=1; for(i=1; i<num_cols; i++) startingPos[i] = startingPos[i=1] + rowTerms[i-1]; for(i=1; i<=numTerms; i++) { j=startingPos[s[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[i].value = a[i].value; } }

7 다차원 배열의 표현 배열의 원소 수 : a[upper0][upper1]….[uppern-1] = 다차원 배열 표현 방법
행 우선 순서(row major order) A[upper0][upper1] 열 우선 순위(column major order) A[0][0] A[0][1] ··· A[0][upper1-1] ···· row0 row1 row2 rowupper0-1 A[0][0] A[1][0] ··· A[upper0-1][0] ···· col0 col1 col2 colupper1-1

8 다차원 배열의 표현 주소 계산 (2차원 배열 – 행우선 표현)
α = A[0][0]의 주소 A[i][0]의 주소 = α + i · upper1 A[i][j]의 주소 = α + i · upper1 + j 주소 계산 (3차원 배열) : A[upper0][upper1][upper2] 2차원 배열 upper1  upper2  upper0개 A[i][0][0] 주소 = α + i · upper1 · upper2 A[i][j][k] 주소 = α + i · upper1 · upper2 + j · upper2 + k A[upper0][upper1]…[uppern-1] α = A[0][0]…[0]의 주소 a[i0][0]…[0] 주소 = α + i0upper1upper2…uppern-1 a[i0][i1][0]…[0] 주소 = α + i0upper1upper2…uppern-1 + i1upper2upper3…uppern-1

9 다차원 배열의 표현 a[i0][i1]…[in-1] 주소 = α + i0upper1upper2…uppern-1
+ in-2uppern-1 + in-1 = α 여기서 : 0≤ j < n-1

10 다항식 다항식의 원형 리스트(circular list) 표현 마지막 노드가 리스트의 첫 번째 노드를 가리키도록 함
(cf) 체인(chain) - 마지막 노드의 링크 필드 값이 NULL인 단순 연결 리스트 3x14+2x8+1의 원현 리스트 표현 제로 다항식(zero polynomial)을 특별한 경우로 처리해야 함 해방된 노드를 체인 형태의 리스트로 유지 가용 공간 리스트(available space list) 혹은 avail 리스트 avail : 해방된 노드들의 리스트에서 첫번째 노드를 가리키는 포인터 초기에 avail은 NULL 새로운 노드가 필요하면 이 리스트를 조사 malloc이나 free를 사용하는 대신 getNode, retNode를 사용 3 14 2 8 1 last

11 다항식 다항식의 원형 리스트 표현 (계속) 헤더 노드(header node) 사용 -
제로 다항식에 대한 특별한 경우를 만들지 않기 위해 각 다항식은 헤더 노드를 갖도록 함 header - - (a) 제로 다항식 header - - 3 14 2 8 1 (b) 3x + 2x + 1 14 8 헤더 노드를 가진 다항식 예

12 polyPointer cpadd(polyPointer a, polyPointer b)
{ /* 다항식 a와 b는 헤더 노드를 가진 단순 연결 원형 리스트이고, a와 b가 합산된 다항식을 반환한다. */ polyPointer startA, c, lastC; int sum, done = FALSE; startA = a; a = a->link; b = b->link; c = getNode(); c->expon = -1; lastC = c; do { switch(COMPARE(a->expon, b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &lastC); b = b->link; break; case 0: /* a->expon = b->expon */ if(startA == a) done = TRUE; else { sum = a->coef + b->coef; if(sum) attach(sum, a->expon, &lastC); a = a->link; b = b->link; } break; case 1: /* a->expon > b->expon */ attach(a->ceof, a->expon, &lastC); a = a->link; }while(!done); lastC->link = c; return c;