第６話 最大値排除繰り返し法マルチスレッド改良版
#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);
void tf1();
void tf2();
void tf3();
void tf4();
int n,*m,ik[4];
int h1,h2,h3,h4,o1,o2,o3,o4;
int main(){
//srand(static_cast<unsigned int>(time(0)));
m=(int *)malloc(2000000);
cout<<"発生させるデータ数をキーボードから入力してください。"<<endl<<"データ数＝";
scanf("%d",&n);
f();
DateTime^ hj=DateTime::Now; //開始時間
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;
}
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 x,int ow){
int i,max,w,ikr;
max=-1;
h1=x;o1=x+(ow-x)/4;
h2=x+(ow-x)/4+1;o2=x+(ow-x)/2;
h3=x+(ow-x)/2+1;o3=x+3*(ow-x)/4;
h4=x+3*(ow-x)/4+1;o4=ow;
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();
for(i=0;i<4;i++){
if(m[ik[i]]>max){
max=m[ik[i]];
ikr=ik[i];
}
}
w=m[x];
m[x]=m[ikr];
m[ikr]=w;
if(x+1<ow-1)g(x+1,ow);
}
void tf1(){
int i,max=0;
for (i=h1;i<o1+1;i++){
if(m[i]>max){
max=m[i];
ik[0]=i;
}
}
}
void tf2(){
int i,max=0;
for (i=h2;i<o2+1;i++){
if(m[i]>max){
max=m[i];
ik[1]=i;
}
}
}
void tf3(){
int i,max=0;
for (i=h3;i<o3+1;i++){
if(m[i]>max){
max=m[i];
ik[2]=i;
}
}
}
void tf4(){
int i,max=0;
for (i=h4;i<o4+1;i++){
if(m[i]>max){
max=m[i];
ik[3]=i;
}
}
}
実行例
前話のデータと比較すると
うーん、うまくいきません。
かなり重くなってしまいました。
結局、隣項交換繰り返し法シングルスレッド、隣項交換繰り返し法マルチスレッド、
最大値排除繰り返し法シングルスレッド、最大値排除繰り返し法マルチスレッドの中で一番速いのは、
最大値排除繰り返し法シングルスレッドであり、それに前話の最大値排除繰り返し法マルチスレッドが次ぐ結果となりました。
なんとなく納得できない結果ですが、諦めてsetとsortによるそれぞれの並び替えへと話題を変えましょう。
第５話へ 第２４講第１話へ
