![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
No.6ベストアンサー
- 回答日時:
CPUの分岐予測が原因ではないでしょうか。
※分岐予測についてはWikipediaを参照してください。
逆順のデータに対しては、常に入れ替え動作をします。
分岐予測の種類によりますが、常に「実行されるとCPUが予測している」なら、パイプラインを最大限に活用して高速な処理を実現できます。
一方、ランダムなデータであれば、分岐結果が一定ではないので予測の失敗が多発します。この場合パイプラインを生かし切れずに性能が劣化します。
今回の場合入れ替え動作自体がごく単純であるがために、予測に失敗することによるオーバーヘッドのほうが大きくなっているのでしょう。
期待する結果を得るには、入れ替え動作自体のオーバーヘッドが大きくなるようにする必要があります。たとえば大きな構造体を使うようにします。
ただし、普通大きな構造体などを利用する場合、ポインタを使います。ポインタであれば入れ替えのオーバーヘッドが小さくなります。
結局、
「適切な分岐予測をするCPUでのバブルソートでは、逆の順序に並べたデータの処理は、ランダムに並んだデータよりも早い」
という結論になります。
参考URL:http://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90% …
回答ありがとうございます。
s117さんの回答と補足資料を見る限り、これが原因であるとみて間違いないようですね。
CPUにはそのような機能もあるんですね、勉強になりました。
ご回答いただきありがとうございました。
No.5
- 回答日時:
>このif文を何回実行しているかを数える方が、
これは正確な回答ではありませんでした。
「このif文を実行した結果が何回真になったか」が正しいです。
つまり、降順にきれいに並んでいるデータと
ランダムに並んでいるデータとで、
実際の入れ替え処理を何回実行したか、を比べてみては?ということです。
この回答への補足
回答ありがとうございます。
if文の下にカウンターをつけて実行したところ、
ランダム順 約25億
降順 約 7億
という結果になりました。
これはコンパイラの処理の仕方によって異なるのかなと考えましたが、s117さんの回答と資料を拝見したところ、CPUの分岐予測が原因ではないかという結論にたどり着きました。
何度もご回答いただき、ありがとうございました。
No.4
- 回答日時:
ソート後のデータを出力するよりも、
>if(str[j-1]>str[j]){
このif文を何回実行しているかを数える方が、
問題解決にとって有益かもしれません。
No.3
- 回答日時:
>バブルソートの部分のソースを提示させていただきます。
提示された箇所以外はこちらで勝手に書いてもいいのですか?
当方で、あなたのところとできるだけ同じ条件で実験するためには、
お手持ちのコードを「そっくりそのまま」載せてくださる方がよいと思います。
いかがでしょうか。
この回答への補足
申し訳ございません。ソースコード全体を提示させていただきます。
#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まで1行づつデータを読み込む
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
よろしくお願いします。
No.2
- 回答日時:
どういったソースコードで実験されたかを提示してください。
この回答への補足
回答ありがとうございます。
バブルソートの部分のソースを提示させていただきます。
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();//クロックストップ
なお、他のソースコードで実験した人も同様の結果になったので、ソースコードが原因ではないと考えています。
No.1
- 回答日時:
>なぜこのようになるのですか?
測定方法(データ数はいくつなのか?、
1回の測定か0、何回かの平均値か?等)、
及び測定環境(CPU, メモリ、OS等)が明示されていないので、
原因は分かりません。
可能性をあげることはできます。
例えば、降順、ランダム、1回きりの場合で
Windows上でシングルCPU(HTもない)で測定した場合に、
たまたま、ランダム測定中に別プロセスにタスク・スイッチが切り替わった。
GetTickCount()での時間測定なので、
他のタスク実行時間も含めて評価してしまった。
とか、
データ数がCPUのキャッシュに全部収まる範囲だったので
後に実行した場合は、キャッシュアクセスで済んでしまった。
等々
何回かの平均をとらないと、比較に耐えるデータにはならないと
おもいますが、平均をとったかいなか文章からは読み取れません。
条件を明示してください。
この回答への補足
回答ありがとうございます。条件が不足していてすいません。
データ数は100000個でそれぞれ3回ずつ実行しました。これは学校の実験で行ったのですが、他の人も同じ結果になっていました。(バブルソートのソースはみんなバラバラです)
OSはLINUXです。メモリ、CPUはわかりません。
使用したコンパイラはgccで、emacsを使用しました。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
教えて下さい
-
メモ帳(テキストデータ)をExc...
-
Accessで該当データにフラグを...
-
VBA 空白セルを削除ではない方...
-
多量のSUMIF式を軽くしたい
-
配列でデータが入っている要素...
-
S9タイプからXタイプにデータ...
-
SASの時間比較
-
【エクセル】測定時間がバラバ...
-
ハミング窓関数とFFT(高速フー...
-
共有メモリへのマッピング(Map...
-
Fortranで/(スラッシュ)を含...
-
<VB>String→Object
-
ブレーカー落ちで壊れたりしな...
-
ビットシフトについて
-
ワイモバイルの速度制限
-
C# ソケット通信でデータ受信時...
-
0が含まれる幾何平均が「#NUM!」
-
VBAを使ってOutlookメール本文...
-
パースとはなんですか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
教えて下さい
-
配列でデータが入っている要素...
-
あんまり考えたくないけど
-
【エクセル】測定時間がバラバ...
-
メモ帳(テキストデータ)をExc...
-
多量のSUMIF式を軽くしたい
-
この行は既に別のテーブルに属...
-
エクセルで2つの時系列のデー...
-
ブレーカー落ちで壊れたりしな...
-
VBA 空白セルを削除ではない方...
-
S9タイプからXタイプにデータ...
-
Accessで該当データにフラグを...
-
EXCELVBAでSQLserverからデータ...
-
CString型の文字列連結について
-
[C言語] コメント文字列を無視...
-
VBAを使ってOutlookメール本文...
-
シーケンサにパソコンからアク...
-
C# ソケット通信でデータ受信時...
-
パースとはなんですか?
-
ユーザーフォームのテキストボ...
おすすめ情報