第23講 並び替えソフトをマルチスレッド化する
第4話 最大値排除繰り返し法をマルチスレッド化するには?
さて、一応隣項交換繰り返し法はマルチスレッド化に成功しました。
その結果、現時点では隣項交換繰り返し法の方が速くなっていると思っていましたら・・・
なんと、コードを次のように変更したら、シングルでも隣項交換繰り返し法マルチスレッド版を遙かに凌いでいます。
#include<iostream>
#include<ctime>
#include<stdlib.h>
using namespace std;
using namespace System;
void f();
void g(int hj,int ow);
int n,*m;
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,ik,w;
max=-1;
for(i=x;i<ow;i++){
if(m[i]>max){
max=m[i];
ik=i;
}
}
w=m[x];
m[x]=m[ik];
m[ik]=w;
if(x+1<ow-1)g(x+1,ow);
}
実行結果
隣項交換繰り返し法のデータ
より遙かに速いですね。
改良箇所で速くなった原因となった箇所はm[i]=rand()%1000;です。
m[i]=rand()%100;の場合は重複データが多いのに対して、
m[i]=rand()%1000;は少なくなります。
マルチ化するまでもなく、決着はついてしまいました。
しかし、マルチ化するとどのぐらい速くなるのかは興味があります。
マルチ化は、隣項交換繰り返し法のときと同様に4グループに分けて並び替えてから、
それを合体することによって実現しましょう。
第3話へ 第5話へ
C言語 C++講義第1部へ
C言語 C++講義第2部へ
VB講義へ
VB講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義(基礎から応用まで)