|
안녕하세요! cedar 김백일입니다.
지난번(2번) 글에 이어서 STL로 행렬을 구현하는 방법에 대한 글입니다.
역시 본격적인 STL 강좌로 보기에는 턱없이(?) 미흡하기 때문에
강좌란이 아니라 Tip'N Tricks에 올립니다.
역시 이번 내용도
Ulrich Breyman(1998), "Designing Components with the C++ STL", Addison-Wesley의
Ch. 9 Vectors and matrices
을 참고했습니다.
===================================================================
지난번 글에는 C의 2차원 배열과 유사한 방법으로 2차원 vector를 사용해서
(물론 deque을 쓸 수도 있습니다.)
행렬을 구현한 예를 보였습니다.
이번에는 메모리 모델(레이아웃)에 따라서 행렬의 원소들을 선형 주소 공간
(linear address space)에 매핑하는 방법에 따라 행렬을 다르게 구현하는
방법에 대한 설명입니다.
행렬에서의 메모리 모델(레이아웃)에 대해서는
보통 자료구조(data structure) 책에서 상당히 앞부분에 나오는 내용입니다.
즉, 1차원 배열에 대한 설명 다음에 바로 나오는 내용이지요.
자세한 내용은 자료구조 관련 서적을 참고하시고요.
간단하게만 설명하겠습니다.
2차원 배열을 선형 주소 공간(linear address space)에 매핑하는 방법은
列 방향 순서(column major order)와 行 방향 순서(row major order)로 나눌 수 있습니다.
列 방향 순서를 사용하는 언어는 포트란이 대표적이며,
行 방향 순서를 사용하는 언어는 포트란을 제외한 C, 파스칼 등의 대부분의 다른 언어들이 있습니다.
그래서 보통 列 방향 순서를 쓰는 메모리 레이아웃을 FORTRAN memory layout이라고 하며,
行 방향 순서를 쓰는 메모리 레이아웃을 C memory layout이라고 합니다.
그 외에도 자주 쓰는 메모리 레이아웃으로, 대칭 행렬(symmetric matrix)이 있는 데,
정사각 행렬 M이
M = M^T (여기서 M^T는 전치(轉置) 행렬(transposed matrix)입니다)
인 성질을 갖는 경우를 말합니다.
즉 행렬의 모든 원소에 대해서 M(i,j) = M(j,i)인 경우입니다.
보통의 정사각 행렬에 필요한 메모리는 r^2 이지만,
대칭 행렬의 경우는 1 + 2 + ... + r = r * (r + 1) / 2 이 됩니다.
예를 들어, 3x3 행렬의 경우를 생각해봅시다.
C Memory layout의 경우는 선형 주소 공간에 다음 순서로 매핑됩니다.
(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)
FORTRAN Memory layout의 경우는 선형 주소 공간에 다음 순서로 매핑됩니다.
(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2)
대칭 행렬의 Memory layout의 경우는 선형 주소 공간에 다음 순서로 매핑됩니다.
(0,0) (0,1) (0,2) (1,1) (1,2) (2,2)
여기서는 하나의 선형 메모리에 대해
위 세가지 메모리 레이아웃을 사용한 행렬을 구현하고자 합니다.
즉, 행렬에 대해 하나의 수퍼클래스 MatrixSuperClass를 정의하고
이 수퍼클래스의 자손인 CMatrix, FortranMatrix, SymmMatrix를 정의합니다.
(여기서 CMatrix는 MFC의 C로 시작하는 클래스들하고는 전혀 관계없습니다. ^^;)
또한 행렬에 사용되는 선형 메모리는 vector와 deque가 가능한데요,
이 각각에 대해 모두 클래스를 정의하는 것은 별로 좋지 않겠죠?
그래서 위의 클래스를 컨테이너 어댑터(container adaptor)로 정의합니다.
컨테이너 어댑터란 다른 STL 컨테이너의 인터페이스를 변경하는 STL 컴포넌트를 말합니다.
반대로 컨테이너 어댑터 자신의 입장에서 보면, 컨테이너 어댑터 클래스 내부의 자료구조(컨테이너)를 다르게 지정할 수 있다는 얘기입니다.
STL에서 기본으로 정의하는 컨테이너 어댑터로 stack, queue, priority_queue,
이 세 가지가 있습니다.
STL 헤더에는 다음과 같이 정의되어 있습니다.
template<typename T, typename Container = deque<T> >
class stack
template<typename T, typename Container = deque<T> >
class queue
template<typename T, typename Container = deque<T> >
class priority_queue
즉, 그냥
stack<int>, queue<int>, priority_queue<int> 라고 쓰면
다음과 같이 deque를 사용해서 구현한 스택, 큐, 우선순위 큐가 만들어집니다.
stack<int, deque<int> >, queue<int, deque<int> >, priority_queue<int, deque<int> >
내부의 자료구조를 vector나 list로 바꾸고 싶으면
stack<int, vector<int> >, queue<int, vector<int> >, priority_queue<int, vector<int> >
stack<int, list<int> >, queue<int, list<int> >, priority_queue<int, list<int> >
로 쓰면 됩니다.
이러한 컨테이너 어댑터를 행렬의 경우에 적용해 보자는 얘기입니다.
그럼 여기까지의 설명에 따라
실제로 구현해 보도록 하겠습니다.
vector와 deque가 무엇인지 정도는 알고 있는 분이시라면
누구나 쉽게 이해할 수 있으실 겁니다.
참고: 위의 Breymann 책에 있는 예제 코드는 너무 복잡한데다가, 빌더에서 런타임 에러가 나더군요.
(Rogue Wave나 STLport 둘 다 마찬가지입니다.)
그래서 코드를 (제 입맛에 맞게) 대폭 수정했습니다.
//
// matrices.h
//
#ifndef MATRICES_H
#define MATRICES_H
#include<cassert> // used in subclasses
#pragma hdrstop
#include<vector>
#include<deque>
using namespace std;
// 다음에 정의할 행렬 클래스들의 수퍼클래스입니다.
// 이 클래스 단독으로는 행렬의 기능을 수행할 수 없기 때문에
// 인스턴스化하지 마세요.
template<typename T, typename Container = vector<T> >
class MatrixSuperClass {
public:
Container C;
size_t Rows() const { return rows; }
size_t Columns() const { return columns; }
MatrixSuperClass(size_t r, size_t c)
: rows(r), columns(c) {}
protected:
size_t rows, columns;
void check_index(size_t r, size_t c) const
{ assert(r < Rows() && c < Columns()); }
};
template<typename T, typename Container = vector<T> >
class CMatrix : public MatrixSuperClass<T, Container> {
public:
CMatrix(size_t r, size_t c)
: MatrixSuperClass<T, Container>(r, c)
{ C.resize(r * c); }
T& operator()(size_t r, size_t c)
{
check_index(r, c);
return C[r * columns + c];
}
};
template<typename T, typename Container = vector<T> >
class FortranMatrix : public MatrixSuperClass<T, Container> {
public:
FortranMatrix(size_t r, size_t c)
: MatrixSuperClass<T, Container>(r, c)
{ C.resize(r * c); }
T& operator()(size_t r, size_t c)
{
check_index(r, c);
// In the address calculation, rows and columns are exchanged
return C[c * rows + r]; // in contrast to the CMatrix class
}
};
template<typename T, typename Container = vector<T> >
class SymmMatrix : public MatrixSuperClass<T, Container> {
public:
SymmMatrix(size_t r, size_t c)
: MatrixSuperClass<T, Container>(r, c)
{
assert(r == c); // matrix must be quadratic
// reduced memory consumption thanks to symmetry
C.resize(r * (r + 1) / 2);
}
// The symmetry is exploited
T& operator()(size_t r, size_t c)
{
assert(r < Rows() && c < Columns());
return r <= c ? C[r + c * (c + 1) / 2]: C[c + r * (r + 1) / 2];
}
};
#endif
다음은 테스트용 코드입니다.
지난번글에서는 행렬의 원소를 접근할 때 C에서와 같이
matrix[1][2] 와 같은 방법을 사용했지만,
여기서는 베이직이나 포트란과 유사한 방법으로
matrix(1,2) 로 사용합니다.
이 행렬의 선형 메모리를 억세스하려면
matrix.C[5] 와 같이 하면 됩니다.
#include <iostream>
#pragma hdrstop
#include <vector>
#include <deque>
#include "matrices.h"
using namespace std;
int main() {
{
CMatrix<float> MC(5,7);
cout << "CMatrix<float, vector<float> >" << endl;
// fill rectangle
for(size_t i = 0; i < MC.Rows(); ++i)
for(size_t j = 0; j < MC.Columns(); ++j)
// application of operator()()}:
MC(i,j) = i + (float)j / 100.0;
// display rectangle
for(size_t i = 0; i < MC.Rows(); ++i) {
for(size_t j = 0; j < MC.Columns(); ++j)
cout << MC(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MC.C.size(); ++i)
cout << MC.C[i] << ' ';
FortranMatrix<float> MF(5,7);
cout << "\n\nFortranMatrix<float, vector<float> > " << endl;
// fill rectangle
for(size_t i = 0; i < MF.Rows(); ++i)
for(size_t j = 0; j < MF.Columns(); ++j)
// application of operator()()}:
MF(i,j) = i + (float)j / 100.0;
// display rectangle
for(size_t i = 0; i < MF.Rows(); ++i) {
for(size_t j = 0; j < MF.Columns(); ++j)
cout << MF(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MC.C.size(); ++i)
cout << MF.C[i] << ' ';
// Example of a symmetric matrix
SymmMatrix<float> MD(5,5);
cout << "\n\nSymmMatrix<float, vector<float> > " << endl;
// fill triangle
for(size_t i = 0; i < MD.Rows(); ++i)
for(size_t j = i; j < MD.Columns(); ++j)
MD(i,j) = i + (float)j / 100.0;
// output square
for(size_t i = 0; i < MD.Rows(); ++i) {
for(size_t j = 0; j < MD.Columns(); ++j)
cout << MD(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MD.C.size(); ++i)
cout << MD.C[i] << ' ';
}
{
CMatrix<float, deque<float> > MC(5,7);
cout << "\n\n\nCMatrix<float, deque<float> >" << endl;
// fill rectangle
for(size_t i = 0; i < MC.Rows(); ++i)
for(size_t j = 0; j < MC.Columns(); ++j)
// application of operator()()}:
MC(i,j) = i + (float)j / 100.0;
// display rectangle
for(size_t i = 0; i < MC.Rows(); ++i) {
for(size_t j = 0; j < MC.Columns(); ++j)
cout << MC(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MC.C.size(); ++i)
cout << MC.C[i] << ' ';
FortranMatrix<float, deque<float> > MF(5,7);
cout << "\n\nFortranMatrix<float, deque<float> > " << endl;
// fill rectangle
for(size_t i = 0; i < MF.Rows(); ++i)
for(size_t j = 0; j < MF.Columns(); ++j)
// application of operator()()}:
MF(i,j) = i + (float)j / 100.0;
// display rectangle
for(size_t i = 0; i < MF.Rows(); ++i) {
for(size_t j = 0; j < MF.Columns(); ++j)
cout << MF(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MC.C.size(); ++i)
cout << MF.C[i] << ' ';
// Example of a symmetric matrix
SymmMatrix<float, deque<float> > MD(5,5);
cout << "\n\nSymmMatrix<float, deque<float> > " << endl;
// fill triangle
for(size_t i = 0; i < MD.Rows(); ++i)
for(size_t j = i; j < MD.Columns(); ++j)
MD(i,j) = i + (float)j / 100.0;
// output square
for(size_t i = 0; i < MD.Rows(); ++i) {
for(size_t j = 0; j < MD.Columns(); ++j)
cout << MD(i,j) << ' ';
cout << endl;
}
cout << endl;
// display linear array
for(size_t i = 0; i < MD.C.size(); ++i)
cout << MD.C[i] << ' ';
}
return 0;
다음은 출력 결과입니다.
CMatrix<float, vector<float> >
0 0.01 0.02 0.03 0.04 0.05 0.06
1 1.01 1.02 1.03 1.04 1.05 1.06
2 2.01 2.02 2.03 2.04 2.05 2.06
3 3.01 3.02 3.03 3.04 3.05 3.06
4 4.01 4.02 4.03 4.04 4.05 4.06
0 0.01 0.02 0.03 0.04 0.05 0.06 1 1.01 1.02 1.03 1.04 1.05 1.06 2 2.01 2.02 2.03
2.04 2.05 2.06 3 3.01 3.02 3.03 3.04 3.05 3.06 4 4.01 4.02 4.03 4.04 4.05 4.06
FortranMatrix<float, vector<float> >
0 0.01 0.02 0.03 0.04 0.05 0.06
1 1.01 1.02 1.03 1.04 1.05 1.06
2 2.01 2.02 2.03 2.04 2.05 2.06
3 3.01 3.02 3.03 3.04 3.05 3.06
4 4.01 4.02 4.03 4.04 4.05 4.06
0 1 2 3 4 0.01 1.01 2.01 3.01 4.01 0.02 1.02 2.02 3.02 4.02 0.03 1.03 2.03 3.03
4.03 0.04 1.04 2.04 3.04 4.04 0.05 1.05 2.05 3.05 4.05 0.06 1.06 2.06 3.06 4.06
SymmMatrix<float, vector<float> >
0 0.01 0.02 0.03 0.04
0.01 1.01 1.02 1.03 1.04
0.02 1.02 2.02 2.03 2.04
0.03 1.03 2.03 3.03 3.04
0.04 1.04 2.04 3.04 4.04
0 0.01 1.01 0.02 1.02 2.02 0.03 1.03 2.03 3.03 0.04 1.04 2.04 3.04 4.04
CMatrix<float, deque<float> >
0 0.01 0.02 0.03 0.04 0.05 0.06
1 1.01 1.02 1.03 1.04 1.05 1.06
2 2.01 2.02 2.03 2.04 2.05 2.06
3 3.01 3.02 3.03 3.04 3.05 3.06
4 4.01 4.02 4.03 4.04 4.05 4.06
0 0.01 0.02 0.03 0.04 0.05 0.06 1 1.01 1.02 1.03 1.04 1.05 1.06 2 2.01 2.02 2.03
2.04 2.05 2.06 3 3.01 3.02 3.03 3.04 3.05 3.06 4 4.01 4.02 4.03 4.04 4.05 4.06
FortranMatrix<float, deque<float> >
0 0.01 0.02 0.03 0.04 0.05 0.06
1 1.01 1.02 1.03 1.04 1.05 1.06
2 2.01 2.02 2.03 2.04 2.05 2.06
3 3.01 3.02 3.03 3.04 3.05 3.06
4 4.01 4.02 4.03 4.04 4.05 4.06
0 1 2 3 4 0.01 1.01 2.01 3.01 4.01 0.02 1.02 2.02 3.02 4.02 0.03 1.03 2.03 3.03
4.03 0.04 1.04 2.04 3.04 4.04 0.05 1.05 2.05 3.05 4.05 0.06 1.06 2.06 3.06 4.06
SymmMatrix<float, deque<float> >
0 0.01 0.02 0.03 0.04
0.01 1.01 1.02 1.03 1.04
0.02 1.02 2.02 2.03 2.04
0.03 1.03 2.03 3.03 3.04
0.04 1.04 2.04 3.04 4.04
0 0.01 1.01 0.02 1.02 2.02 0.03 1.03 2.03 3.03 0.04 1.04 2.04 3.04 4.04
|
