C++에서
STL을 이용하여
희소행렬(sparse matrix)을 구현한다면, 원소를 저장하기에 가장 좋은 자료형은 뭘까? 아마 map일 거다. 키를 위치 인덱스로 하고, 데이터에는 실제 값을 넣으면 된다.
STL엔 두 개의 map이 있다. 하나는
std::map이고, 다른 하나는
std::unordered_map이다. 이들의 용도는 다음과 같이 간단히 정리할 수 있다. 킷값에 따라 정렬해주는 map이 필요하다면
std::map을 사용하고, 빠른 검색이 필요하다면
std::unordered_map을 사용한다. 우린 키를 정렬할 필요는 없으므로,
std::unordered_map을 이용하기로 하자.
이제 2차원 인덱스를 표현할 자료형을 결정해야 한다. C++의 내장 배열을 사용하자니 번거롭고,
std::vector를 사용하자니 너무 무겁다.
2011년 8월 12일에 제정된 새로운 C++ 표준에선
std::array를 정의하고 있다. 이건, 고정된 크기의
std::vector라고 생각하면 되는데,
std::vector보다 가볍고 C++ 내장 배열보다 편리하다. 행렬의 인덱스는 길이가 2로 고정되므로
std::array는 인덱스의 자료형에 딱 맞는 컨테이너이다.
이제 구현을 해보자. 먼저, 필요한 헤더를 불러온다.
// smat.cc
#include <array>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <unordered_map>
cstdlib 헤더는
main 함수의 반환 값으로 사용할
EXIT_SUCCESS 매크로를 정의가 들어 있고,
numeric 헤더는 해시 값 생성에 사용할
accumulate 함수의 선언이 들어 있다.
다음으로 할 일은
함수자(functor)를 만드는 것이다.
std::unordered_map은
해시표를 사용하는 데, 키로부터 해시 값을 계산해서 해시표를 생성해야 한다. 기본 자료형에 대해서는 해시 값을 생성하는 함수자가 이미 선언되어 있지만, 그 외의 자료형에 대해선 우리가 직접 만들어줘야 한다.
std::unary_function을 이용해서 간단하게 인덱스의 두 값을 더하는 해시 함수자를 만든다.
namespace std
{
template <>
struct hash<array<int, 2> >: public unary_function<array<int, 2>, size_t>
{
size_t operator()(const array<int, 2>& idx) const
{
return accumulate(idx.begin(), idx.end(), 0);
}
};
}
이제 희소행렬 자체를 구현할 클래스를 선언한다. 행렬 연산을 구현하는 여러 함수도 구현해야겠지만, 여기선 행렬 원소의 읽기와 쓰기에 관련된 연산자 정도만 구현해보자.
template <typename T> class SparseMatrix
{
public:
SparseMatrix(int i, int j): i_size(i), j_size(j) {}
T& operator()(int i, int j)
{
std::array<int, 2> idx;
idx[0] = i;
idx[1] = j;
return mat[idx];
}
T operator()(int i, int j) const
{
std::array<int, 2> idx;
idx[0] = i;
idx[1] = j;
typename std::unordered_map<std::array<int, 2>, T>::const_iterator tmp;
tmp = mat.find(idx);
if (tmp == mat.end())
return T();
else
return tmp->second;
}
private:
std::unordered_map<std::array<int, 2>, T> mat;
std::size_t i_size, j_size;
};
눈여겨볼 점은 행렬의 원소를 설정할 때 사용할
operator()와 원소를 조회할 때 사용할
operator() const를 모두 선언해야 한다는 것이다.
operator()만 선언한다면, 행렬의 원소를 조회할 때마다 조회하는 인덱스에 해당하는 항목을 map에 만들게 된다. 예를 들어,
SparseMatrix<double> sm(3, 3);
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
std::cout << sm(i, j) << " ";
}
std::cout << std::endl;
}
처럼 모든 원소를 조회하기만 해도 내부 저장 장소인
mat에 모든 원소에 해당하는 항목이 만들어져 메모리를 낭비하게 된다.
실제로 원소를 설정하고 조회하는 방법은 아래와 같다.
using namespace std;
int main(int argc, char* argv[])
{
SparseMatrix<double> sm(3, 3);
sm(1, 2) = 1;
sm(2, 0) = 2;
const SparseMatrix<double>& sm_ref = sm;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << sm_ref(i, j) << " ";
}
cout << endl;
}
return EXIT_SUCCESS;
}
operator() const를 호출하려면, 상수 레퍼런스나 상수 포인터를 이용해서
SpareMatrix에 접근해야 한다. 뭐, 대충 이렇다. 이 코드는 C++0x 표준인
std::array와
std::unordered_map을 사용하는데, 이 기능이 시험적으로 구현된 거라서 이용하면 컴파일 할 때
-std=c++0x 옵션을 줘야 한다.
$ g++ -Wall -g -pedantic -std=c++0x -o smat smat.cc
실행해보면, 잘 작동하는 것을 확인할 수 있다.
$ ./smat
0 0 0
0 0 1
2 0 0
$
mat의 크기를 검사해 보면, 단 두 개의 항목만 저장하고 있는 것을 확인할 수 있다. 간단한 희소행렬 완성!
