ADT : Sparse Matrices, Multidimensional Arrays

Sparse Matrices (희소 행렬)

매트릭스의 구현은 두가지 방식이 있다. 하나는 dense, 다른 하나는 sparse 이다.

 

(task에 따라 필요한 매트릭스가 달라짐.)

sparse 매트릭스의 구현을 알아보도록 하자.

m개의 행과 n개의 열로 이루어져 있다. 총 m과 n개의 개수로 이루어져 있다.

그냥 이차원 배열로 구현할 경우, 공간이 낭비될 수 있다.

매트릭스의 operations으로 Creation, Transpose, Addition, Multiplication 구현해야 함.

 

구현 방식

row와 col 그리고 값을 활용해서 구성 요소를 특징으로 갖을 수 있다.

행(row)에 의해 오름차순으로 정렬되고 임의의 행에 대한 정보는 열(col)이 오름차순이 되도록 저장된다. (그러니까 같은 행(row)에 있을 경우 열(col)을 기준으로 정렬 됨.)

명령이 종료되기 위해, 행과 열, 값을 가진 요소의 개수를 알아야 한다.

 

SparseMatrix에 MatrixTerm이 포함되어 있는 구조.

SparseMatrix의 내부 구조

rows : 행의 개수, cols : 열의 개수, terms : 0이 아닌 항의 총 개수, capacity : smArray의 크기

 

smArray 구조 (전치 행렬 만들기)

전치행렬의 경우 row와 col을 바꿔주기만 하면된다. 

(i,j,value) -> (j,i,value)

(row)으로 정렬, 행번호가 같을 경우 열(col)을 오름차선으로 정렬. (순서를 꼭 유지해야 함.)

매번 정렬해주어야 하기 때문에 시간적인 비용 발생 O(terms*cols) terms을 정렬, cols를 정렬.

 

우리가 아래와 같이 2차원 배열(dense maxtix)로 구현했을 때는 O(rows*cols)가 됨

우리가 위처럼 transpose를 구현하면 최악의 경우 위와 같이 간단히 구현된 것보다 훨씬 많은 비용이 소모될 수 있음

 

전치 행렬 만들기 (개선)

매트릭스의 각 열에 해당하는 요소의 개수를 센다면, (0열엔 ~개, 1열엔 ~개)

transepose 매트릭스에 각 행의 개수를 구할 수 있다.

위와 같이 원래 매트릭스의 col의 개수를 세면 새로운 전치행렬의 시작 위치를 알 수 있음.

이렇게 원래의 매트릭스에서 해당하는 열을 검색해서 전치 매트릭스로 하나씩 이동시켜주면 됨.

그러면 시간을 O(columns + terms)로 바꿀 수 있음.

 

Representation of Arrays

고차원행렬 a[u1][u2],..,[un]가 있다고 가정하자. 총 구성 요소의 개수는 아래와 같다.

마지막 index가 a[1][2][1][1] 라면 2 * 3* 3* 2 = 24이다.

아래와 같은 형태로 바꿀 수 있다.

이 것을 1차원 배열로 변환해보자.

그러면 

위와 같이 저장할 수 있다.

 

이차원 배열

이차원 배열 a의 주소는 a[0][0]이며

a+[0][i] 는 처음 주소 + i로 접근 (행 순서로)

a[i][0] 이것이 처음 주소 + i*u2의 길이로 순서대로 접근할 수 있다. (열순서로)

a[i][j] 처음 주소 + i*u2 + j의 개수.

 

삼차원 배열

삼차원 배열은 위와 같이 접근할 수 있다.

 

고차원 배열

위와 같은 법칙이 성립한다.

 

결국 메모리의 주소가 핵심인듯?