マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第11章 マルチスレッドプログラミング
第16話 第15話課題シングルスレッド版魔方陣自動生成のコード例
#pragma warning(disable: 4996)//第２編のために必要
#include<iostream>//インクルードファイルiostreamの読み込み
#include<conio.h>//while(!_kbhit());を使うためのお呪い
#include<string> //文字列変数を使えるようにするために組み込む
#include <iomanip> //setprecisionを使えるように組み込む
#include <cmath>//powなどを使うときに必要
#include <ctime>//time()（←現時刻発生する関数）を使うために必要
using namespace std;//coutを使うときに必要なお呪い
#include <process.h>//_beginthreadを使うために必要
const size_t n = 4;
const size_t th = n * n;
void f(int p, int s);//魔方陣生成関数
void ２次座標生成();
size_t m[7040][th][n][n];//魔方陣を収納する４次元配列
size_t a[th][n][n];//魔方陣を形成するための作業用３次元配列
size_t cn[th];//それぞれのスレッドにおける魔方陣をカウントする１次元配列
size_t y[th];//縦座標
size_t x[th];//横座標
size_t b[n][n];//y座標・x座標形成のための２次元配列
size_t mg = n * (th + 1) / 2;//魔方陣の対角線または行または列の合計
int main() {
clock_t hj, ow;
for (size_t i = 0; i < th; i++) {
cn[i] = 0;
}
２次座標生成();
cout << "シングルスレッド版" << n
<< "次魔方陣検証開始" << endl <<
endl;
hj = clock();
for (size_t i = 0; i < th; i++) {
a[i][y[0]][x[0]] = i + 1;
f(i, 1);
}
ow = clock();
for (size_t i = 0; i < 100; i++) {
for (size_t j = 0; j < th;
j++) {
for
(size_t k = 0; k < n; k++) {
for (size_t l = 0; l < n; l++) {
if (m[i][j][k][l] < 10) {
cout << " " << m[i][j][k][l] << " ";
}
else {
cout << m[i][j][k][l] << " ";
}
}
cout << endl;
}
cout
<< endl;
}
cout << endl;
}
cout << n << "次魔方陣生成時間は"
<< (double)(ow - hj) / CLOCKS_PER_SEC << "秒です。" << endl;
size_t gk = 0;
for (size_t i = 0; i < th; i++) {
gk += cn[i];
}
cout << "生成された" << n
<< "次魔方陣個数は" << gk <<
"個です。" << endl;
cout << "シングルスレッド版" << n
<< "次魔方陣検証全過程修了" << endl;
while (!_kbhit());//待機させるための命令
return(0);
}
void f(int p, int s) {//魔方陣生成関数
for (size_t i = 0; i < th; i++) {
size_t h = 1;
for (size_t j = 0; j < s;
j++) {
if (a[p][y[j]][x[j]]
== i + 1) {
h = 0;
break;
}
}
if (h == 1) {
a[p][y[s]][x[s]]
= i + 1;
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][n - 1 - j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== 0 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
> 0 && y[s] < n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 2 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][x[s]];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] > 0 && x[s] < n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][x[s]];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (s
+ 1 < th) {
f(p, s + 1);
}
else
{
for (size_t j = 0; j < th; j++) {
m[cn[p]][p][y[j]][x[j]] = a[p][y[j]][x[j]];
}
cn[p]++;
/*if (cn[p] == 100) {
a[p][y[s]][x[s]] = 0;
return;
}*/
}
}
/*if (cn[p] == 100) {
a[p][y[s]][x[s]]
= 0;
return;
}*/
a[p][y[s]][x[s]] = 0;
}
}
void ２次座標生成() {//y横座標とx縦座標生成
int i, j, c;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
b[i][j]
= -1;
}
}
for (i = 0; i < n; i++) {
b[i][i] = i;
}
c = n - 1;
for (i = 0; i < n; i++) {
if (b[i][n - 1 - i] == -1) {
c++;
b[i][n
- 1 - i] = c;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (b[i][j]
== -1) {
c++;
b[i][j] = c;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
x[b[i][j]]
= j;
y[b[i][j]]
= i;
}
}
}
void 変身の術関数(void*
aa) {//マルチスレッド
size_t p = *(size_t*)aa;
a[p][y[0]][x[0]] = p + 1;
f(p, 1);
}
void f(int p, int s) {//魔方陣生成関数
for (size_t i = 0; i < th; i++) {
size_t h = 1;
for (size_t j = 0; j < s;
j++) {
if (a[p][y[j]][x[j]]
== i + 1) {
h = 0;
break;
}
}
if (h == 1) {
a[p][y[s]][x[s]]
= i + 1;
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][n - 1 - j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== 0 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
> 0 && y[s] < n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 2 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][x[s]];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] > 0 && x[s] < n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][j][x[s]];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (y[s]
== n - 1 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計
+= a[p][y[s]][j];
}
if (合計
!= mg)h = 0;
}
}
if (h == 1) {
if (s
+ 1 < th) {
f(p, s + 1);
}
else
{
for (size_t j = 0; j < th; j++) {
m[cn[p]][p][y[j]][x[j]] = a[p][y[j]][x[j]];
}
cn[p]++;
/*if (cn[p] == 100) {
a[p][y[s]][x[s]] = 0;
return;
}*/
}
}
/*if (cn[p] == 100) {
a[p][y[s]][x[s]]
= 0;
return;
}*/
a[p][y[s]][x[s]] = 0;
}
}
void ２次座標生成() {//y横座標とx縦座標生成
int i, j, c;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
b[i][j]
= -1;
}
}
for (i = 0; i < n; i++) {
b[i][i] = i;
}
c = n - 1;
for (i = 0; i < n; i++) {
if (b[i][n - 1 - i] == -1) {
c++;
b[i][n
- 1 - i] = c;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (b[i][j]
== -1) {
c++;
b[i][j] = c;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
x[b[i][j]]
= j;
y[b[i][j]]
= i;
}
}
}
実行結果
(
10 15 6 3
5 4 9 16
11 14 7 2
8 1 12 13
11 16 1 6
14 3 10 7
4 13 8 9
5 2 15 12
12 14 1 7
13 3 16 2
4 6 9 15
5 11 8 10
13 12 1 8
7 2 11 14
4 5 16 9
10 15 6 3
14 15 1 4
2 3 13 16
11 10 8 5
7 6 12 9
15 13 4 2
1 3 16 14
8 6 9 11
10 12 5 7
16 13 1 4
2 3 15 14
11 10 6 7
5 8 12 9
4次魔方陣生成時間は14.021秒です。
生成された4次魔方陣個数は7040個です。
シングルスレッド版4次魔方陣全過程修了
)
マルチスレッド版は
魔方陣生成時間は3.233秒です。
生成された魔方陣個数は7040個です。
マルチスレッド版全課程修了
ですから、速度比較は14.021÷3.233 = 4.3倍です。
実験によって結果は異なり3.7倍のときもありましたから、
およそ４倍です。
16倍まではいきません。
素数生成のときと同じで総数7040では正しい結果は期待できません。
そこで、皆さんは
if (cn[p] == 100) {
a[p][y[s]][x[s]] = 0;
return;
}
部分も注釈文規定を外して const size_t n = 5; const size_t n = 6; 等と変更して
実験してみましょう。ただし、６次ではかなり時間がかかりますので、
就寝前に実行して次の朝に結果を確認するとよいと思います。
果たして５次魔方陣25スレッド、６次魔方陣36スレッドでは何倍になるのでしょうか。
第11章第15話へ 第11章17話へ
本講義トップへ