C++로 간단하게 구현해보는 희소행렬

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의 크기를 검사해 보면, 단 두 개의 항목만 저장하고 있는 것을 확인할 수 있다. 간단한 희소행렬 완성!