ホーム » 2011 » 1月 » 19

日別アーカイブ: 2011年1月19日

2011年1月
« 12月   2月 »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

C++0xを使う

前述のグラフのプログラムで、隣接行列を"vector< bitset<8> > a ;"で宣言すると、 その初期化において、"a.push_back( bitset<8>( … ) ;" を使って、 手作業で要素を初期化していた。 文法的にも、ややこしそうなものをクラスに渡すことになるし、しかたがないと思っていた。 でも、改めてC++の解説を読んでいたら、C++0xであれば、使えそうな文法が…

// bitsetのベクトル
vector< bitset<N> > a = {
bitset<N>( 0x02 ) ,
bitset<N>( 0x0D ) ,
bitset<N>( 0x42 ) ,
bitset<N>( 0x12 ) ,
bitset<N>( 0x28 ) ,
bitset<N>( 0xD0 ) ,
bitset<N>( 0xA4 ) ,
bitset<N>( 0x60 ) ,
} ;

ただし、この機能は、g++4.4.5であれば、"error: in C++98 'a' must be initialized…" とエラーが 表示されてしまう。コンパイルするときには、次のように書くみたい。

$ g++ -std=c++0x graph-bitset.cxx

C++0xを読んでいたら、LISP屋の飛びつくラムダ式なんてのが書いてあったので、 思わず試さずにはいられなかった。

vector<int> a = {
1,2,3,4,5
} ;
int main() {
int sum = 0 ;
for_each( a.begin() ,
a.end() ,
[&sum]( int x ) {
sum += x ;
} ) ;
return 0 ;
}

試してみたけど、動かんじゃん….でも調べてみると、g++4.5以降とな…

グラフ探索

例年だと解説していないんだけど、大学編入試験あたりで出題されている場合もあるし、 探索方法にこだわらなければ、難しい内容でもないので、グラフについて説明。

(0)--(1)--(3)--(4)--(5)--(7)
|              |    |
(2)------------(6)---+

上図のような、ノード間の接続状況を覚える場合、各ノードの接続を0/1で覚える 隣接行列がよく使われる。この例では、無向グラフだけれど、 ノードi番からj番につながっているものをa[i][j]=1で覚えれば、 有向グラフでも扱える。 実際のプログラミングでは、ノードを駅、路線を隣接行列で覚えるが、 隣接行列に、駅間の運賃を保存する場合も考えられる。(重み付きグラフ)

この隣接行列で、始点を与えた時のすべての経路を求めるプログラムは、 以下のようになる。

#include <stdio.h>
#define N 8
int a[N][N] = { // 隣接行列(無向グラフ)
{0,1,0,0,0,0,0,0} ,
{1,0,1,1,0,0,0,0} ,
{0,1,0,0,0,0,1,0} ,
{0,1,0,0,1,0,0,0} ,
{0,0,0,1,0,1,0,0} ,
{0,0,0,0,1,0,1,1} ,
{0,0,1,0,0,1,0,1} ,
{0,0,0,0,0,1,1,0}
} ;
// 訪問フラグ
int flag[N] = {0,0,0,0,0,0,0,0} ;
void visit( int i ) {
flag[i] = 1 ;
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

このプログラムでは、訪問可能な先が、未訪問であれば訪問する…という処理を、 再帰によって行っている。

メモリ節約のために2進数で…

このプログラムでは、隣接行列や訪問フラグには、0/1の論理値しか保存していないのに、 int型(32bit-CPUで4byte)を消費してもったいない。 論理値0/1の配列を、2進数のbit列で扱えば、メモリを節約できる。
# 節約目的というより、2進数の取り扱いは、情報処理試験や
# 大学の編入試験での出題もあるから…

各種試験を考えると、下の赤線部あたりが理解できる/書けるというのがキモ。

#define N 8
int a[N] = {
0x02 , // {0,1,0,0,0,0,0,0} → 0000,0010
0x0D , // {1,0,1,1,0,0,0,0} → 0000,1101
0x42 , // {0,1,0,0,0,0,1,0} → 0100,0010
0x12 , // {0,1,0,0,1,0,0,0} → 0001,0010
0x28 , // {0,0,0,1,0,1,0,0} → 0010,1000
0xD0 , // {0,0,0,0,1,0,1,1} → 1101,0000
0xA4 , // {0,0,1,0,0,1,0,1} → 1010,0100
0x60 , // {0,0,0,0,0,1,1,0} → 0110,0000
} ;
int flag = 0 ;
void visit( int i ) {
flag |= (1<<i) ;
for( int j = 0 ; j < N ; j++ ) {
if ( (a[i] & (1<<j)) && (flag & (1<<j))==0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

ちょうど、C++のテンプレートなどを使ったプログラミングを確認していたので、 STLを使って書いてみた。 配列宣言とか初期化以外の部分は、最初のプログラムと同じように書けるのが C++のテンプレート機能のおかげ。 bitsetは、論理値の配列を内部的にはbit演算で行ってくれるクラス。 vectorは、指定型で配列サイズが動的なもの。

#include <iostream>
#include <bitset>
#include <vector>
#define N 8
using namespace std;
vector< bitset<N> > a ;
bitset<N>           flag( 0x00 ) ;
void visit( int i ) { // 最初のプログラムとまるっきり同じ
flag[i] = 1 ;       // 内部的にはbitsetのおかげで2進数演算
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
cout << i << "->" << j << " " ;
visit( j ) ;
}
}
}
int main() {
a.push_back( bitset<N>( 0x02 ) ) ;
a.push_back( bitset<N>( 0x0D ) ) ;
a.push_back( bitset<N>( 0x42 ) ) ;
a.push_back( bitset<N>( 0x12 ) ) ;
a.push_back( bitset<N>( 0x28 ) ) ;
a.push_back( bitset<N>( 0xD0 ) ) ;
a.push_back( bitset<N>( 0xA4 ) ) ;
a.push_back( bitset<N>( 0x60 ) ) ;
visit(0) ;
return 0 ;
}

プログラム末尾の配列a[]の初期化が、ちょっと美しくない。 C++では、配列は、無引数のデフォルトコンストラクタで初期化される。 しかし、引数付きで初期化したい時もあるんで、調べてみたら、 "placement new"なんて機能があるみたい。

vector< bitset<N> > a( 8 ) ;
int table[N] = {
0x02 , 0x0D , 0x42 , 0x12 , 0x28 , 0xD0 , 0xA4 , 0x60 ,
} ;
int main() {
for( int i = 0 ; i < N ; i++ )
new( &a[i] ) bitset<N>( table[i] ) ;
:
}

たしかに便利なコンストラクタの強制呼び出しなんだけど、 このコードだと、要素についてデフォルトコンストラクタと、 placement new のコンストラクタの2回が呼び出される。 placement new の実行前に、デストラクタって呼び出されるの? なんか気持ち悪い…
# 試してみたけど、placement new の前にデストラクタが呼ばれることはないようだ…