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 の前にデストラクタが呼ばれることはないようだ…