バブルソートの実行時間について

バブルソートで降順、ランダム順に並んでいるデータを読み込ませて昇順に並び替える実行時間について質問です。

バブルソートにおける計算時間は、データ数が多いほど、並び替える回数が多いほど長くなるはずですが、実際に実行したところ、並び替える回数が多いはずの降順のほうがランダム順よりも早くなりました。

なぜこのようになるのですか？

よろしくお願いします。

No.6 ベストアンサー 回答者： S117 回答日時： 2009/05/17 00:53

CPUの分岐予測が原因ではないでしょうか。

※分岐予測についてはWikipediaを参照してください。

逆順のデータに対しては、常に入れ替え動作をします。
分岐予測の種類によりますが、常に「実行されるとCPUが予測している」なら、パイプラインを最大限に活用して高速な処理を実現できます。

一方、ランダムなデータであれば、分岐結果が一定ではないので予測の失敗が多発します。この場合パイプラインを生かし切れずに性能が劣化します。

今回の場合入れ替え動作自体がごく単純であるがために、予測に失敗することによるオーバーヘッドのほうが大きくなっているのでしょう。

期待する結果を得るには、入れ替え動作自体のオーバーヘッドが大きくなるようにする必要があります。たとえば大きな構造体を使うようにします。

ただし、普通大きな構造体などを利用する場合、ポインタを使います。ポインタであれば入れ替えのオーバーヘッドが小さくなります。
結局、
「適切な分岐予測をするCPUでのバブルソートでは、逆の順序に並べたデータの処理は、ランダムに並んだデータよりも早い」
という結論になります。

参考URL：http://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90% …

この回答へのお礼

回答ありがとうございます。

s117さんの回答と補足資料を見る限り、これが原因であるとみて間違いないようですね。
CPUにはそのような機能もあるんですね、勉強になりました。

ご回答いただきありがとうございました。

お礼日時：2009/05/17 01:28

No.5 回答者： asuncion 回答日時： 2009/05/16 23:54

＞このif文を何回実行しているかを数える方が、

これは正確な回答ではありませんでした。
「このif文を実行した結果が何回真になったか」が正しいです。
つまり、降順にきれいに並んでいるデータと
ランダムに並んでいるデータとで、
実際の入れ替え処理を何回実行したか、を比べてみては？ということです。

この回答への補足

回答ありがとうございます。

if文の下にカウンターをつけて実行したところ、
ランダム順　約２５億
降順　　　　約　７億
という結果になりました。

これはコンパイラの処理の仕方によって異なるのかなと考えましたが、s117さんの回答と資料を拝見したところ、CPUの分岐予測が原因ではないかという結論にたどり着きました。

何度もご回答いただき、ありがとうございました。

補足日時：2009/05/17 01:21

この回答へのお礼

すいません、こちらに書くべきでしたね。

何度もご回答いただき、ありがとうございました。

お礼日時：2009/05/17 01:24

No.4 回答者： asuncion 回答日時： 2009/05/16 23:25

ソート後のデータを出力するよりも、

＞if(str[j-1]>str[j]){

このif文を何回実行しているかを数える方が、
問題解決にとって有益かもしれません。

No.3 回答者： asuncion 回答日時： 2009/05/16 20:47

＞バブルソートの部分のソースを提示させていただきます。

提示された箇所以外はこちらで勝手に書いてもいいのですか？
当方で、あなたのところとできるだけ同じ条件で実験するためには、
お手持ちのコードを「そっくりそのまま」載せてくださる方がよいと思います。
いかがでしょうか。

この回答への補足

申し訳ございません。ソースコード全体を提示させていただきます。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(int argc,char **argv){
int i,j,temp;
int count=0;
int str[1000000];
clock_t c_start,c_end;
FILE *fp;

if(argc!=2){
fprintf(stderr,"File has not been opened\n");
exit(1);
}

if((fp=fopen(argv[1],"r"))==NULL){//ファイルを読み込む
fprintf(stderr,"File has not been opened\n");
exit(1);
}

while(fscanf(fp,"%d",&str[count]) != EOF) {//EOFまで１行づつデータを読み込む
count++;
}

c_start=clock();//クロックスタート

for(i=0;i<count;i++){//バブルソートを行う
for(j=count;j>i;j--){
if(str[j-1]>str[j]){
temp=str[j];
str[j]=str[j-1];
str[j-1]=temp;
}//End if
}//End for j
}//End for i

c_end=clock();//クロックストップ

printf("permute it in ascending order\n");

for(i=0;i<count;i++) printf("%d\n",str[i]);//ソート後のデータを出力する

printf("Time:%f\n",(double)(c_end-c_start)/CLOCKS_PER_SEC);//実行時間の出力

return 0;

}//End main

よろしくお願いします。

補足日時：2009/05/16 20:50

No.2 回答者： asuncion 回答日時： 2009/05/16 20:31

どういったソースコードで実験されたかを提示してください。

この回答への補足

回答ありがとうございます。

バブルソートの部分のソースを提示させていただきます。

c_start=clock();//クロックスタート

for(i=0;i<count;i++){//count=データ数
for(j=count;j>i;j--){
if(str[j-1]>str[j]){
temp=str[j];
str[j]=str[j-1];
str[j-1]=temp;
}//End if
}//End for j
}//End for i

c_end=clock();//クロックストップ

なお、他のソースコードで実験した人も同様の結果になったので、ソースコードが原因ではないと考えています。

補足日時：2009/05/16 20:40

No.1 回答者： BLK314 回答日時： 2009/05/16 20:13

>なぜこのようになるのですか？

測定方法（データ数はいくつなのか？、
１回の測定か0、何回かの平均値か？等）、
及び測定環境(CPU, メモリ、OS等)が明示されていないので、
原因は分かりません。

可能性をあげることはできます。

例えば、降順、ランダム、１回きりの場合で
Windows上でシングルCPU(HTもない)で測定した場合に、
たまたま、ランダム測定中に別プロセスにタスク・スイッチが切り替わった。
GetTickCount()での時間測定なので、
他のタスク実行時間も含めて評価してしまった。

とか、

データ数がCPUのキャッシュに全部収まる範囲だったので
後に実行した場合は、キャッシュアクセスで済んでしまった。

等々

何回かの平均をとらないと、比較に耐えるデータにはならないと
おもいますが、平均をとったかいなか文章からは読み取れません。

条件を明示してください。

この回答への補足

回答ありがとうございます。条件が不足していてすいません。

データ数は100000個でそれぞれ３回ずつ実行しました。これは学校の実験で行ったのですが、他の人も同じ結果になっていました。（バブルソートのソースはみんなバラバラです）

OSはLINUXです。メモリ、ＣＰＵはわかりません。

使用したコンパイラはgccで、emacsを使用しました。

よろしくお願いします。

補足日時：2009/05/16 20:30