희소행렬 (sparse matrix)

행렬은 m개의 행과 n개의 열로 이루어진 2차원 데이터 객체로, 총 m x n 개의 값이 있습니다. 만약 행렬의 대부분의 요소가 0 값을 갖는다면, 이를 희소 행렬(sparse matrix)이라고 합니다.

 

희소 행렬을 사용하는 이유

• 저장 용량: 0이 아닌 요소가 0인 요소보다 적기 때문에, 이러한 요소들만 저장하여 용량을 줄일 수 있습니다.
• 계산 시간: 0이 아닌 요소들만 탐색하여 논리적인 데이터 구조를 설계함으로써 계산 시간을 줄일 수 있습니다.

 

 

 

희소행렬 예시:

 

0 0 3 0 4            
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0

 

2차원 배열을 사용하여 희소 행렬을 나타내면 대부분의 경우 0인 원소들은 사용되지 않으므로 많은 메모리 낭비가 발생합니다. 따라서 0이 아닌 원소들만 저장하도록 하여 메모리를 절약할 수 있습니다. 이는 (행, 열, 값) 세 개의 트리플 형태로 저장하는 것을 의미합니다.

희소 행렬 표현의 일반적인 방법

1. 배열 표현
2. 연결 리스트 표현

 

방법 1: 배열 사용 (COO)

2차원 배열을 사용하여 희소 행렬을 표현하며, 다음과 같은 세 개의 행이 있습니다.

 

• 행(Row): 0이 아닌 원소가 위치한 행의 인덱스
• 열(Column): 0이 아닌 원소가 위치한 열의 인덱스
• 값(Value): (행, 열) 위치에 있는 0이 아닌 원소의 값

 

 

 

배열방식 사용 후 결과는 아래와 같습니다.

0 0 1 1 3 3
 2 4 2 3 1 2
 3 4 5 7 2 6

 

 

방법 2: 연결 리스트 사용 (CSR)

 

연결 리스트에서 각 노드는 네 개의 필드를 갖습니다. 이 네 개의 필드는 다음과 같이 정의됩니다.

 

• 행(Row): 0이 아닌 원소가 위치한 행의 인덱스
• 열(Column): 0이 아닌 원소가 위치한 열의 인덱스
• 값(Value): (행, 열) 위치에 있는 0이 아닌 원소의 값
• 다음 노드(Next node): 다음 노드의 주소

 

 

연결 리스트 처리 후 결과는 아래와 같습니다.

 

row_position:0 0 1 1 3 3 
column_position:2 4 2 3 1 2 
Value:3 4 5 7 2 6