第３話 隣項交換繰り返し法自己再帰版マルチスレッド版
コード例
#include<iostream>
#include<ctime>
#include<stdlib.h>
using namespace std;
using namespace System;
using namespace System::Threading;
void f();
void g(int hj,int ow);
int h(int p,int x,int a);
void tf1();
void tf2();
void tf3();
void tf4();
int *m;
int n;
int cn[5];
int main(){
cout<<"マルチスレッド版"<<endl;
//srand(static_cast<unsigned int>(time(0)));
m=(int *)malloc(2000000);
cout<<"発生させるデータ数をキーボードから入力してください。"<<endl<<"データ数＝";
scanf("%d",&n);
f();
DateTime^ hj=DateTime::Now; //開始時間
Thread^ t1=gcnew Thread(gcnew ThreadStart(tf1));
Thread^ t2=gcnew Thread(gcnew ThreadStart(tf2));
Thread^ t3=gcnew Thread(gcnew ThreadStart(tf3));
Thread^ t4=gcnew Thread(gcnew ThreadStart(tf4));
t1->Start();
t2->Start();
t3->Start();
t4->Start();
t1->Join();
t2->Join();
t3->Join();
t4->Join();
g(0,n);
DateTime^ ow=DateTime::Now; //終了時間
TimeSpan sa=ow->Subtract(*hj); //経過時間の計算
cout<<"並び替え後"<<endl;
int i=0;
while(i<n){
if(m[i]<10)cout<<" "<<m[i]<<" ";
if(m[i]>=10 && m[i]<100)cout<<" "<<m[i]<<" ";
if(m[i]>=100)cout<<m[i]<<" ";
if(i>0 && (i+1)%15==0)cout<<endl;
i++;
}
cout<<endl;
cout<<"マルチスレッド版"<<endl;
cout<<"データ数"<<n<<"の場合"<<endl;
cout<<"並び替え時間は"<<sa.TotalSeconds<<"秒です。"<<endl;
int max=0;
for(i=0;i<4;i++){
if(max<cn[i])max=cn[i];
}
cout<<"並び替え巡回数は"<<max+cn[4]<<"です。"<<endl;
}
void tf1(){
g(0,n/4);
}
void tf2(){
g(n/4+1,n/2);
}
void tf3(){
g(n/2+1,3*n/4);
}
void tf4(){
g(3*n/4+1,n);
}
void f(){
int i;
i=0;
while(i<n){
m[i]=rand()%1000;
if(m[i]<10)cout<<" "<<m[i]<<" ";
if(m[i]>=10 && m[i]<100)cout<<" "<<m[i]<<" ";
if(m[i]>=100)cout<<m[i]<<" ";
if(i>0 && (i+1)%15==0)cout<<endl;
i++;
}
cout<<endl;
}
void g(int hj,int ow){
char t=1;
int i;
while(t){
if(h(0,hj,ow)==0)t=0;
if(hj==0 && ow==n/4)cn[0]++;
if(hj==n/4)cn[1]++;
if(hj==n/2)cn[2]++;
if(hj==3*n/4)cn[3]++;
if(hj==0 && ow==n)cn[4]++;
}
}
int h(int p,int x,int a){
int w;
if(m[x]<m[x+1]){
p++;
w=m[x];
m[x]=m[x+1];
m[x+1]=w;
}
if(x+1<a-1){
p+=h(p,x+1,a);
}
else{
return(p);
}
return(p);
}
シングルスレッドとのデータ比較
数倍の効果はありませんでしたが、約１．３倍になりました。
巡回数は、ほんの少しですが小さくなっています。
第２話へ 第４話へ
