제2장 배열과구조.

Presentation on theme: "제2장 배열과구조."— Presentation transcript:

1 제2장 배열과구조

2 2.4 희소행렬 추상데이터타입 희소 행렬(Sparse matrix) 0 1 0 0 0 0 0 1 2 3 4 5
0  1    0  0   0   0          0 11  3  0  0   0 0  0    0   0 0  0  0  0  0   0 91  0  0  0  0   0 0    0  0    0 1 2 3 4 5

3 2.4 희소행렬 추상데이터타입 • m × n matrix A ≡ A[MAX_ROWS][MAX_COLS]
# of non-zero elements             <<  small # of total elements        

4 2.4 희소행렬 추상데이터타입 Structure Sparse_Matrix
Objects : 3원소쌍 <행,열,값>의 집합이다. 여기서, 행과 열은 정수이고 이 조합은 유일하며, 값은 item 집합의 한 원소이다. Functions : 모든 a,b∈Sparse_Matrix, x∈item, i , j, max_col, max_row ∈index에 대해 Sparse_Matrix Create(max_row, max_col)  ::= return max_items까지      저장할 수 있는 Sparse_matrix, 여기서 최대 행의 수는 max_row이고 최대 열의 수는 max_col이라 할 때 max_items=max_row*max_col이다. Sparse_Matrix Transpose(a)   ::= return 모든 3원소쌍의 행과 열의 값      을 교환하여 얻은 행렬

5 2.4 희소행렬 추상데이터타입 Sparse_Matrix Add(a,b) ::= if a와 b의 차원이 같으면
return 대응항들, 즉 똑같은 행과 열의 값을 가진 항들을 더해서 만들어진 행렬 else return 오류 Sparse_Matrix Multiply(a,b)   ::= if a의 열의 수와 b의 행의 수가 같으면 return 다음 공식에 따라 a와 b를 곱해서 생성된 행렬 d:d[i][j]=(a[i][j] *b[i][j]), 여기서 d[i][j]는 (i,j)번째 요소이다      else return 오류 end Sparse_Matrix

6 2.4 희소행렬 추상데이터타입 효율적 기억장소 사상 <i, j, value> : 3-tuples (triples)
 효율적 기억장소 사상 <i, j, value> : 3-tuples (triples) no. of rows no. of columns no. of non-zero elements ordering(column major or row major)

7 2.4 희소행렬 추상데이터타입 희소 행렬 0  1    0  0   0   0          0 11  3  0  0   0 0  0    0   0 0  0  0  0  0   0 91  0  0  0  0   0 0    0  0    0 row col value   0 1 1 1 1 11 2 3 -6 3 0 91 5 2 28 1 2 3 4 5 1 2 3 4 5

8 2.4 희소행렬 추상데이터타입 행렬을 위한 연산 행렬의 생성 덧셈 곱셈 전치

9 2.4 희소행렬 추상데이터타입 행렬의 전치(Matrix Transpose) for j← 1 to n do
for i←1 to m do           B(j, i) ← A(i, j)            end                        end

10 2.4 희소행렬 추상데이터타입           1    2      3               1    2      3  A(0,    6,   6,     8         B(0,   6,   6,     8      (1,    0,   0,     15          (1,   0,   0,     15 (2,    0,   3,     22          (2,   0,    4,     91 (3,    0,   5,     -15        (3,   1,   1,     11 (4,    1,   1,     11         (4.   2,   1,     3 (5,    1,   2,     3          (5,   2,   5,     28 (6,    2,   3,     -6          (6,   3,   0,     22 (7,    4,   0,     91         (7,   3,   2,     -6 (8,    5,   2,     28         (8,   5,   0,     -15 행내에서 => 행우선, 열내에서 => 열우선

11 2.4 희소행렬 추상데이터타입 희소 행렬의 전치 각 행 i에 대해서 원소 <i, j, 값>을 가져와서
전치행렬의 원소 <j, i, 값>으로 저장

12 procedure TRANSPOSE(A,B)
//A is a matrix represented in sparse form// //B is set to be its transpose// 1   (m,n,t)←(A(0,1),A(0,2),A(0,3)) 2   (B(0,1),B(0,2),B(0,3))←(n,m,t) 3   if t<0 then return //check for zero matrix// 4   q←1      //q is position if next term in B// 5   for col←1 to n do  //transpose by columns// 6     for p←1 to t do //for all nonzero terms do// 7       if A(p,2)=col       //correct column// 8         then[(B(q,1),B(q,2),B(q,3)) ← //insert// 9              (A(p,2),A(p,1),A(p,3)) //next term//   10                 q←q+1  ]                  11   end 12  end 13 end TRANSPOSE

13 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++; } O(columns * elements)

14 void fast_transpose(term a[], term b[])
{ /* a를 전치시켜 b에 저장 */ int row_terms[MAX_COL], starting_pos[MAX_COL]; int i,j, num_col = 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) { /* 0이 아닌 행렬 */ 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; }                 } O(columns + elements)

15 2.5 다차원 배열의 표현 배열의 원소 수 : a[upper0][upper1]....[uppern-1]
=  ∏i-0,n-1 upperi  -  a[10][10][10] ⇨ 10・10・10 = 1000

16 2.5 다차원 배열의 표현 다차원 배열 표현 방법 - 행 우선 순서(row major order)
              row0            row1       rowupper0-1 - 열 우선 순서(column major order)               col0                col1        colupper1-1 A[0][0] A[0][1] … A[0][upper1-1] A[1][0] … A[0][0] A[1][0] … A[upper1-1][0] A[1][1] …

17 2.5 다차원 배열의 표현 주소 계산 (2차원 배열 - 행우선 표현) α = A[0][0]의 주소
A[i][0]의 주소 = α + i・upper1 A[i][j]의 주소 = α + i・upper1 + j

18 2.5 다차원 배열의 표현 주소 계산 (3차원 배열) : A[upper0][upper1][upper2]
a[i][0][0] 주소 = α+i・upper1・upper2 a[i][j][k] 주소 = α+i・upper1・upper2+j・ upper2 + k

19 2.5 다차원 배열의 표현 A[upper0][upper1]...[uppern-1] α = A[0][0]...[0]의 주소
a[i0][0]...[0] 주소 = α + i0upperCupper2...uppern-1 a[i0][i1][0]...[0] 주소  = α+ i0upper1upper2...uppern-1 + i1upper2upper3...uppern-1 a[i0][i1]...[in-1] 주소 = α + i0upper1upper2...uppern-1 + i1upper2upper3...uppern-1 + i2upper3upper4...uppern-1 ⋮ + in-2uppern-1 + in-1

20 과제물 배열의 전치를 위한 두가지 알고리즘 P/G