再訂正ライフゲームで在来と省エネ型ソースコード
再訂正ライフゲームで在来と省エネ型ソースコード
2024年10月4初稿
エッセイ『ライフゲームで在来と省エネ型ソースコード』で
紹介したソースコードに明らかにミスが有ります!
と訂正したエッセイ『訂正ライフゲームで在来と省エネ型
ソースコード』にも残念ながら「ミス」を発見しました?!
「訂正」で「漸次として処理すればOKと思ったが、2枚の
ステージで交互に繰り返すアルゴリズムが正しいので全面的
に変更しました!」と記載しましたが、その「2枚の
ステージで交互に」で「漸次として1枚ステージ処理」から
ソノママのアルゴリズムで見落としが、ありました?!
以下に示した「code:問題の箇所」と其れを修正した
「code:訂正」を見比べて下さい!
言い訳「ソースコードの作成はTRY&ERRORが基本で
ソースコードを作成する技法を学ぶ教育として【項羽と劉邦
の名将だが俺様強すぎて人望が無い項羽依り、馬に乗れば落
ちると揶揄われる駄目な親分劉邦が秦滅亡後、漢の高祖と呼
大人物と崇めラレル故事】に則って失敗を多く乗せる事にし
ました」と言い訳させてね?!
code:問題の箇所
/* 問題が有る場所:教科書的なソースコード */
if( 3 == sum ){ /* セル誕生条件なら */
putCELL( x, y, 1 ); /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
} /* if構文の終端 */
/* 問題が有る場所:ポインタ多用したソースコード */
if( 3 == sum ){ /* セル誕生条件なら */
*pwx = 1; /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
} /* if構文の終端 */
code:訂正
/* 問題が有る場所解決策:教科書的なソースコード */
if( 3 == sum ){ /* セル誕生条件なら */
putCELL( x, y, 1 ); /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else{ /* 条件が外れ≒状態が不変 */
putCELL( x, y, getCELL( x, y) ); /* ビフォーをアフターへコピー */
} /* if構文の終端 */
/* 問題が有る場所解決策:ポインタ多用したソースコード */
if( 3 == sum ){ /* セル誕生条件なら */
*pwx = 1; /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
}else{ /* 条件が外れ≒状態が不変 */
*pwx = *prx; /* ビフォーをアフターへコピー */
} /* if構文の終端 */
エッセイ『現在のデーターセンターに置ける省エネ型コン
ピューターを考察』の補足の為に具体的なソースコードとし
て「ライフゲーム」と言う良く知られている物を使用!
ライフゲームでは初期状態のみでその後の状態が決定される
碁盤のような格子があり、一つの格子はセル(細胞)と呼ば
れる。各セルには8つの近傍のセルがある (ムーア近傍) 。
各セルには「生」と「死」の2つの状態があり、あるセルの
次のステップ(世代)の状態は周囲の8つのセルの今の世代
における状態により決定される。
セルの生死は次のルールに従う。
誕生
死んでいるセルに隣接する生きたセルがちょうど3つあれば
次の世代が誕生する。
生存
生きているセルに隣接する生きたセルが2つか3つならば、
次の世代でも生存する。
過疎
生きているセルに隣接する生きたセルが1つ以下ならば、
過疎により死滅する。
過密
生きているセルに隣接する生きたセルが4つ以上ならば、
過密により死滅する。
下に中央のセルにおける次のステップでの生死の例を示す。
生きているセルは■、死んでいるセルは□で表す。
1.教科書的なソースコード
code:在来型ソースコード
/*ライフゲームで在来型ソースコード*/
/*ライフゲームで在来型CPU使用例在来型ソースコード*/
#include <stdio.h> /* 標準的なC言語システムヘッダ */
#define HSIZE 1000 /* 水平方向サイズが1000*/
#define VSIZE 1000 /* 垂直方向サイズが1000*/
typedef unsigned char CELL; /* 生死情報型名 */
CELL stage[1000000]; /* ライフゲームの実現ステージとし縦横1000×1000サイズ領域 */
CELL temp[1000000]; /* ライフゲームの実現ステージとし縦横1000×1000サイズ領域 */
/* ライフゲームが二つの状態のビフォーアフターを繰り返すので */
/* 一時的な作業ステージとして用意 */
int flag; /* 二つのステージ≪stage[]・temp[]≫の読み書き指定フラッグ */
/* flag=0⇒「stage[]から読み、temp[]へ書き込み」 */
/* flag=1⇒「temp[]から読み、stage[]へ書き込み」 */
/* ステージをクリア≪全て生者が無い状態に初期化≫ */
void ClearStage(void) /* 仮引数も関数返値も無い */
{
int i; /* カウンタ:インデックス */
for( i = 0; i < 1000000; i++ ){ /* お馴染みforループ構文で1000000回繰り返す */
stage[i] = 0; /* ライフゲームの実現ステージに生者が無い状態=0セット */
temp[i] = 0; /* ライフゲームの実現ステージに生者が無い状態=0セット */
} /* forループ構文終端 */
flag = 0; /* flag=0⇒「stage[]から読み、temp[]へ書き込み」 */
}
/* ライフゲームの実現ステージ≪1次元データ配列の記録領域だが2次元と見なす≫縦横を */
/* 2次元座標XY指定で位置の生死セル状態を取出する関数 */
int getCELL( int x, int y ){ /* 仮引数で座標XY指定 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
return( stage[ x + y * HSIZE] ); /* 1次元データを2次元と見なしてアクセスしてデータ取出 */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
return( temp[ x + y * HSIZE] ); /* 1次元データを2次元と見なしてアクセスしてデータ取出 */
} /* if構文終端 */
}
/* ライフゲームの実現ステージ≪1次元データ配列の記録領域だが2次元と見なす≫縦横を */
/* 2次元座標XY指定で位置の生死セル状態変更(セット)する関数 */
void putCELL( int x, int y, int d ){ /* 仮引数で座標XY指定と生死データ指定、関数返値は無い */
if( 0 != flag ){ /* flag=1⇒「stage[]へ書き込み」の場合 */
stage[ x + y * HSIZE] = d; /* 1次元データを2次元と見なしてアクセスしてデータを */
/* 状態変更(セット) */
}else{ /* flag=0⇒「temp[]へ書き込みtemp[]」の場合 */
temp[ x + y * HSIZE] = d; /* 1次元データを2次元と見なしてアクセスしてデータを */
/* 状態変更(セット) */
} /* if構文終端 */
}
/* ライフゲームの一世代進行≪世代交代≫ */
/* ★備考★極、教科書で記載する様なソースコード */
void generationalChange(void) /* 仮引数も関数返値も無い */
{
int x; /* 横(水平或はX座標)方向の位置 */
int y; /* 縦(垂直或はY座標)方向の位置 */
int sum; /* 注視点の生死判定する隣接セル生死把握の為の生セル合計 */
for( y = 1; y < (VSIZE-1); y++ ){ /* 2重ループの外側「縦(垂直)方向Y」増加ループ */
for( x = 0; x < (HSIZE-1); x++ ){ /* 2重ループの内側「横(水平)方向X」増加ループ */
sum = getCELL( x - 1, y - 1 ) /* 注視点の斜め左上隣 */
+= getCELL( x, y - 1 ) /* 注視点の上隣 */
+= getCELL( x + 1, y - 1 ) /* 注視点の斜め右上隣 */
+= getCELL( x - 1, y ) /* 注視点の左隣 */
+= getCELL( x + 1, y ) /* 注視点の右隣 */
+= getCELL( x - 1, y + 1 ) /* 注視点の斜め左下隣 */
+= getCELL( x, y + 1 ) /* 注視点の下隣 */
+= getCELL( x + 1, y + 1 ); /* 注視点の斜め右下隣と注視点周辺生セル合計 */
if( 3 == sum ){ /* セル誕生条件なら */
putCELL( x, y, 1 ); /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else{ /* 条件が外れ≒状態が不変 */
putCELL( x, y, getCELL( x, y) );/* ビフォーをアフターへコピー */
} /* if構文の終端 */
} /* 内側「横(水平)方向X」増加ループ終端 */
} /* 外側「縦(垂直)方向Y」増加ループ終端 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
flag = 1; /* 表裏反転 */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
flag = 0; /* 表裏反転 */
} /* if構文終端 */
}
/* ライフゲームの結果印刷 */
/* ★備考★極、教科書で記載する様なソースコード */
void PrintStage( /* 結果をプリントアウト */
int x; /* X座標 */
int x; /* Y座標 */
int h; /* 水平(X座標)方向サイズ */
int v; /* 垂直(Y座標)方向サイズ */
){
char buf[1000]; /* 印刷用文字列バッファ */
int i; /* インデックス・カウンタ */
int j; /* インデックス・カウンタ */
for( j = 0; j < v; j++, y++ ){ /* 先頭(上)から垂直(Y座標)方向サイズ印刷ループ */
for( i = 0; i < h; i++ ){ /* 印刷用文字列バッファを */
buf[i] = 0; /* 0クリア */
} /* for構文(バッファクリア)終端*/
for( i = 0; i < h; i++ ){ /* 先頭(最左側)から水平(X座標)方向サイズセル印刷ループ */
if( 0 == getCELL( x, y ) ){ /* セルに死者しか無い */
buf[x+i] = ' '; /* 文字「空白」をバッファにセット */
}else{ /* セルに生者発見 */
buf[x+i] = '*'; /* 文字「アスタリスク」をバッファにセット */
} /* if構文終端 */
} /* for構文(X座標)終端 */
printf( "%s\n", buf ); /* 文字バッファを印刷 */
} /* for構文(Y座標)終端 */
}
/* ライフゲームの遊び方 */
void example1(void) /* 例文1 */
{
char buf[100]; /* 印刷用文字列バッファ */
int i; /* インデックス・カウンタ */
int x; /* X座標 */
int y; /* Y座標 */
ClearStage(); /* 全て死の世界 */
putCELL( 1, 1, 1 ); /* 生者をセット */
putCELL( 2, 1, 1 ); /* 生者をセット */
putCELL( 3, 1, 1 ); /* 生者をセット */
putCELL( 1, 2, 1 ); /* 生者をセット */
putCELL( 1, 3, 1 ); /* 生者をセット */
PrintStage( 0, 0, 100, 100 ); /* 先頭(左上)から100×100セル印刷 */
generationalChange(); /* ライフゲームの一世代進行 */
PrintStage( 0, 0, 100, 100 ); /* 先頭(左上)から100×100セル印刷 */
}
在来型CPUでの在来型ソースコードで取り敢えず
ライフゲームのプログラムを作成して見ました!
省エネ型は、引き続き、このエッセイに記載しますが、
先ずは、理解して頂く為にここまでとします!
2.私の画像処理ライブラリに多用しているポインタ多用の
ソースコード
code:在来型ソースコードポインタ使用版
/* ライフゲームの一世代進行≪世代交代≫ */
/* ★備考★私が画像処理ライブラリ開発に使用した高速化処理ソースコード方式 */
void generationalChange(void) /* 仮引数も関数返値も無い */
{
int x; /* 横(水平或はX座標)方向の位置カウンタ */
int y; /* 縦(垂直或はY座標)方向の位置カウンタ */
CELL* prx; /* 横(水平或はX座標)方向の位置をポインタ変数表現:読込用 */
CELL* pry; /* 縦(垂直或はY座標)方向の位置をポインタ変数表現:読込用 */
CELL* pwx; /* 横(水平或はX座標)方向の位置をポインタ変数表現:書込用 */
CELL* pwy; /* 縦(垂直或はY座標)方向の位置をポインタ変数表現:書込用 */
int sum; /* 注視点の生死判定する隣接セル生死把握の為の生セル合計 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
pry = stage + 1 + HSIZE; /* ポインタ原点:読込用をセット */
pwy = temp + 1 + HSIZE; /* ポインタ原点:書込用をセット */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
pry = temp + 1 + HSIZE; /* ポインタ原点:読込用をセット */
pwy = stage + 1 + HSIZE; /* ポインタ原点:書込用をセット */
} /* if構文終端 */
for( y = VSIZE-2; --y >= 0; pry += HSIZE, pwy += HSIZE ){ /* 2重ループの外側「縦(垂直)方向Y」増加ループ */
prx = pry; /* 「横(水平)方向X」ポインタ原点:読込用をセット */
pwx = pwy; /* 「横(水平)方向X」ポインタ原点:書込用をセット */
for( x = HSIZE-2; --x >= 0; prx++, pwx++ ){ /* 2重ループの内側「横(水平)方向X」増加ループ */
sum = *(prx - 1 - HSIZE ) /* 注視点の斜め左上隣 */
+= *(prx - HSIZE ) /* 注視点の上隣 */
+= *(prx + 1 - HSIZE ) /* 注視点の斜め右上隣 */
+= *(prx - 1 ) /* 注視点の左隣 */
+= *(prx + 1 ) /* 注視点の右隣 */
+= *(prx - 1 + HSIZE ) /* 注視点の斜め左下隣 */
+= *(prx + HSIZE ) /* 注視点の下隣 */
+= *(prx+ 1 + HSIZE ); /* 注視点の斜め右下隣 */
if( 3 == sum ){ /* セル誕生条件なら */
*pwx = 1; /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
*pwx = 0; /* 死滅≪セルの値を「0」にセット≫ */
}else{ /* 条件が外れ≒状態が不変 */
*pwx = *prx; /* ビフォーをアフターへコピー */
} /* if構文の終端 */
} /* 内側「横(水平)方向X」増加ループ終端 */
} /* 外側「縦(垂直)方向Y」増加ループ終端 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
flag = 1; /* 表裏反転 */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
flag = 0; /* 表裏反転 */
} /* if構文終端 */
}
3.省エネ型≪セルをビットアクセスでメモリー使用量を1/8にした≫
ソースコード
code:省エネ型ソースコード
/*ライフゲームで省エネ型ソースコード*/
/*ライフゲームで在来型CPU使用例省エネ型ソースコード*/
#include <stdio.h> /* 標準的なC言語システムヘッダ */
#define HSIZE 1000 /* 水平方向サイズが1000*/
#define VSIZE 1000 /* 垂直方向サイズが1000*/
typedef unsigned char CELL; /* 生死情報型名「但し、水平方向8個セル」 */
CELL stage[125000]; /* ライフゲームの実現ステージとし縦横1000×1000÷8サイズ領域 */
CELL temp[125000]; /* ライフゲームの実現ステージとし縦横1000×1000÷8サイズ領域 */
/* ライフゲームが二つの状態のビフォーアフターを繰り返すので */
/* 一時的な作業ステージとして用意 */
int flag; /* 二つのステージ≪stage[]・temp[]≫の読み書き指定フラッグ */
/* flag=0⇒「stage[]から読み、temp[]へ書き込み」 */
/* flag=1⇒「temp[]から読み、stage[]へ書き込み」 */
/* ステージをクリア≪全て生者が無い状態に初期化≫ */
void ClearStage(void) /* 仮引数も関数返値も無い */
{
int i; /* カウンタ:インデックス */
for( i = 0; i < 125000; i++ ){ /* お馴染みforループ構文で125000回繰り返す */
stage[i] = 0; /* ライフゲームの実現ステージに生者が無い状態=0セット */
temp[i] = 0; /* ライフゲームの実現ステージに生者が無い状態=0セット */
} /* forループ構文終端 */
flag = 0; /* flag=0⇒「stage[]から読み、temp[]へ書き込み」 */
}
/* ライフゲームの実現ステージ≪1次元データ配列の記録領域だが2次元と見なす≫縦横を */
/* 2次元座標XY指定で位置の生死セル状態を取出する関数 */
int getCELL( int x, int y ){ /* 仮引数で座標XY指定、関数辺値「0,1」状態取り出し */
static int tbl[] = { /* 定数テーブル */
1, 2, 4, 8, 16, 32, 64, 128, /* 2のベキ乗パターン≒ビット有り */
}; /* 定数テーブルの最後「}」*/
int ixPos; /* 配列内位置 */
int bitPos; /* ビット位置 */
int data; /* 水平方向8個セル状態のデータ */
ixPos = x / 8 + y * HSIZE / 8; /* 配列内位置算出 */
bitPos = x % 8; /* ビット位置算出 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
data = stage[ ixPos ]; /* 水平方向8個セル状態のデータ取り出し */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
data = temp[ ixPos ]; /* 水平方向8個セル状態のデータ取り出し */
} /* if構文終端 */
if( 0 != data & tbl[bitPos] ){ /* ビット個別「0,1」状態取り出し「≠0」なら */
return( 1 ); /* 関数辺値「1」をセル=1と見なし1を返す */
}else{ /* ビット個別「0,1」状態取り出し「=0」なら */
return( 0 ); /* ここまで通過したら、セル=0と見なし0を返す */
} /* if構文終端 */
}
/* ライフゲームの実現ステージ≪1次元データ配列の記録領域だが2次元と見なす≫縦横を */
/* 2次元座標XY指定で位置の生死セル状態変更(セット)する関数 */
void putCELL( int x, int y, int d ){ /* 仮引数で座標XY指定と生死データ指定、関数返値は無い */
static int tbl[] = { /* 定数テーブル */
1, 2, 4, 8, 16, 32, 64, 128, /* 2のベキ乗パターン≒ビット有り */
}; /* 定数テーブルの最後「}」*/
int ixPos; /* 配列内位置 */
int bitPos; /* ビット位置 */
int data; /* 水平方向8個セル状態のデータ */
ixPos = x / 8 + y * HSIZE / 8; /* 配列内位置算出 */
bitPos = x % 8; /* ビット位置算出 */
if( 0 != d ){ /* ビット個別「0,1」状態セットする場合なら */
d = 255; /* 255=「bit0からbit7まで1の状態の十進数表現」*/
} /* if構文終端 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
data = stage[ ixPos ]; /* 水平方向8個セル状態のデータ取り出し */
stage[ ixPos ] |= tbl[ bitPos ] ; /* ビット位置にデータ「0,1」セット */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
data = temp[ ixPos ]; /* 水平方向8個セル状態のデータ取り出し */
temp[ ixPos ] |= tbl[ bitPos ] ; /* ビット位置にデータ「0,1」セット */
} /* if構文終端 */
}
/* ライフゲームの一世代進行≪世代交代≫ */
/* ★備考★極、教科書で記載する様なソースコード */
void generationalChange(void) /* 仮引数も関数返値も無い */
{
int x; /* 横(水平或はX座標)方向の位置 */
int y; /* 縦(垂直或はY座標)方向の位置 */
int sum; /* 注視点の生死判定する隣接セル生死把握の為の生セル合計 */
for( y = 1; y < VSIZE-1; y++ ){ /* 2重ループの外側「縦(垂直)方向Y」増加ループ */
for( x = 1; x < HSIZE-1; x++ ){ /* 2重ループの内側「横(水平)方向X」増加ループ */
sum = getCELL( x - 1, y - 1 ) /* 注視点の斜め左上隣 */
+= getCELL( x, y - 1 ) /* 注視点の上隣 */
+= getCELL( x + 1, y - 1 ) /* 注視点の斜め右上隣 */
+= getCELL( x - 1, y ) /* 注視点の左隣 */
+= getCELL( x + 1, y ) /* 注視点の右隣 */
+= getCELL( x - 1, y + 1 ) /* 注視点の斜め左下隣 */
+= getCELL( x, y + 1 ) /* 注視点の下隣 */
+= getCELL( x + 1, y + 1 ); /* 注視点の斜め右下隣と注視点周辺生セル合計 */
if( 3 == sum ){ /* セル誕生条件なら */
putCELL( x, y, 1 ); /* 誕生≪セルの値を「1」にセット≫ */
}else if( 1 <= sum ){ /* 過疎条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else if( 4 >= sum ){ /* 過密条件ならば */
putCELL( x, y, 0 ); /* 死滅≪セルの値を「0」にセット≫ */
}else{ /* 条件が外れ≒状態が不変 */
putCELL( x, y, getCELL( x, y) );/* ビフォーをアフターへコピー */
} /* if構文の終端 */
} /* 内側「横(水平)方向X」増加ループ終端 */
} /* 外側「縦(垂直)方向Y」増加ループ終端 */
if( 0 == flag ){ /* flag=0⇒「stage[]から読み」の場合 */
flag = 1; /* 表裏反転 */
}else{ /* flag=1⇒「temp[]から読み」の場合 */
flag = 0; /* 表裏反転 */
} /* if構文終端 */
}
/*ライフゲームで省エネ型ソースコードをエッセイ『
現在のデーターセンターに置ける省エネ型コンピューターを考察』で紹介したビットアクセスが可能な
CPUで且つ、コンパイラが「bit」と記したビットアクセス型に対応している場合のソースコード*/
/*ライフゲームで改良型CPU使用例省エネ型ソースコード*/
#include <stdio.h> /* 標準的なC言語システムヘッダ */
#define HSIZE 1000 /* 水平方向サイズが1000*/
#define VSIZE 1000 /* 垂直方向サイズが1000*/
typedef bit CELL; /* 生死情報型名「ビット単位アクセス用」 */
CELL stage[1000000]; /* ライフゲームの実現ステージとし縦横1000×1000サイズ領域 */
CELL temp[1000000]; /* ライフゲームの実現ステージとし縦横1000×1000サイズ領域 */
/* ライフゲームが二つの状態のビフォーアフターを繰り返すので */
/* 一時的な作業ステージとして用意 */
int flag; /* 二つのステージ≪stage[]・temp[]≫の読み書き指定フラッグ */
/* flag=0⇒「stage[]から読み、temp[]へ書き込み」 */
/* flag=1⇒「temp[]から読み、stage[]へ書き込み」 */
/* 備考:実行する関数は、型「CELL」を使用して居るのでソースコードは同じです!
ポイントでアクセスするソースコードでもソノママで使用出来る筈です!勿論、コンパイラが対応している
との前提条件で記載しました! */