質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

2回答

3990閲覧

【バブルソート】ランダムデータと降順データの実行時間がおかしい

Sugatail

総合スコア11

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

0グッド

2クリップ

投稿2019/10/19 08:08

編集2019/10/21 04:01

前提

C言語でバブルソートの評価を行いました。

ランダムなデータと降順のデータ(データ数2500,10000,40000)を昇順にソートして、実行時間・交換回数を計測しました。

結果は以下の通り。

実行時間(ms)25001000040000
ランダム8.09203.913928.74
降順8.29113.651832.24
交換回数(回)25001000040000
ランダム154502324960941398801402
降順312375049995000799980000

[追記]
データはint型の整数で、テキストデータからint型配列へ読み出しています。
また実行時間はソートの開始から終了までを図っています。

問題

降順の方が実行時間が短くすんでいる理由が分かりません。

交換回数を見る限り、降順の方が時間がかかりそうなものですが…。
ご教授願えればと思います。

c

1#include <stdio.h> 2#include <stdlib.h> 3#include <string.h> 4#include <sys/time.h> 5#include "data.h" 6 7int swap_counter=0; 8int comparison_counter=0; 9 10/* 要素の交換 */ 11void swap(int *a, int i, int j) { 12 int t = a[i]; 13 a[i] = a[j]; 14 a[j] = t; 15#if defined(VERBOSE_MODE) || defined(COUNT_SWAP) 16 swap_counter++; 17#endif 18} 19 20/* バブルソート */ 21void bubblesort(int *a, int size) { 22 int i, j; 23 for(i=size-1; i>0; i--) { 24 for(j=0; j<i; j++) { 25#if defined(VERBOSE_MODE) || defined(COUNT_COMPARISON) 26 comparison_counter++; 27#endif 28 if (a[j]>a[j+1]) { 29 swap(a, j, j+1); 30 } 31 } 32 } 33} 34 35/* 時間計測 */ 36double get_time() { 37 struct timeval tv; 38 gettimeofday(&tv, NULL); 39 return tv.tv_sec + (double)tv.tv_usec*1e-6; 40} 41 42/* 使用法の表示 */ 43void print_usage() { 44 fprintf(stderr, "usage: bubblesort data\n"); 45} 46 47 48int main(int argc, char* argv[]) { 49 if (argc != 2) { 50 print_usage(); 51 exit(1); 52 } 53 54 FILE *fp = fopen(argv[1], "r"); 55 if (fp == NULL) { 56 fprintf(stderr, "File not found %s\n", argv[1]); 57 exit(1); 58 } 59 int size = read_size(fp); 60 int* data = read_data(fp, size); 61 fclose(fp); 62 63#ifdef VERBOSE_MODE 64 printf("ソート前\n"); 65 print_data(data, size); 66#endif 67 68 double starting_time = get_time(); 69 bubblesort(data, size); // ソート 70 double end_time = get_time(); 71 double consumed_time_in_msec = (end_time-starting_time) * 1000; 72 73#ifdef VERBOSE_MODE 74 printf("\nソート後\n"); 75 print_data(data, size); 76#endif 77 78#ifdef VERBOSE_MODE 79 printf("size: %d\n", size); 80 printf("swap: %d\n", swap_counter); 81 printf("comparison: %d\n", comparison_counter); 82 printf("time (msec): %f\n", consumed_time_in_msec); 83#else 84 85#ifdef COUNT_SWAP 86 printf("%d", swap_counter); 87#endif 88#ifdef COUNT_COMPARISON 89 printf("%d", comparison_counter); 90#endif 91#if !defined(COUNT_SWAP) && !defined(COUNT_COMPARISON) 92 printf("%f", consumed_time_in_msec); 93#endif 94 95#endif 96 97 free_data(data); 98} 99

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cateye

2019/10/19 08:16

システムやCPUが不明ですが、今時のCPUなら隣接データはキャッシュに乗るので処理が早い可能性が有ります。
Zuishin

2019/10/19 08:41

ソースを提示してください。
Sugatail

2019/10/19 09:16

隣接データがキャッシュに乗る ->比較の際に片方を取りに行くだけでもう一方もついてくる ->常に隣同士を比較する降順の方が速い ということでしょうか。
Zuishin

2019/10/19 09:26

ソースを提示してください。
Zuishin

2019/10/19 09:27

もしかして焼きそばソースか何かのことだと思っていますか?
Sugatail

2019/10/19 09:30

すみません、いまお湯ないんです…。
cateye

2019/10/19 09:34 編集

最近のCPUのキャッシュ構造は分からない(CPUのマニュアルがないw)のですが、キャッシュ・ラインというのは通常8〜16ワード(ワードはレジスタのビット長)あって、それを一気に読み込みます。従って、1ワード読むと後続(実際は8バイトとか切りの良いアドレスからフィッチします)データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので(データの読み込みの)処理速度が上がります。
Zuishin

2019/10/19 09:33

なんだ荒らしか。
Sugatail

2019/10/22 02:29 編集

cateyeさん、腑に落ちました。ありがとうございました。 ソース、明日載せますねー。
cateye

2019/10/19 09:41 編集

まぁ、キャシュだけではない気もしますが・・・(別の問題だったりしますから)Zuishinの仰るようにソースを提示されれば、解決の糸口に成るかもです・・・ #バブルソートは少ないデータでしか使ったことがない・・・構造体で20〜30ぐらいか^^;
swordone

2019/10/21 02:24

「比較回数」ってどうやって見ているんですか? 単純に要素同士を大小比較した回数のことを言うのであれば、バブルソートのアルゴリズムでは、元のデータの並びによって比較回数が変化することはありえないと思うのですが…
Sugatail

2019/10/21 02:28

交換回数の間違いでした。 直しておきました。
swordone

2019/10/21 02:29

表のほうが直っていません
Sugatail

2019/10/21 02:30

ごもっともでした。
Sugatail

2019/10/21 02:48 編集

cateyeさんの 「最近のCPUのキャッシュ構造は分からない(CPUのマニュアルがないw)のですが、キャッシュ・ラインというのは通常8〜16ワード(ワードはレジスタのビット長)あって、それを一気に読み込みます。従って、1ワード読むと後続(実際は8バイトとか切りの良いアドレスからフィッチします)データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので(データの読み込みの)処理速度が上がります。」 という理由で納得できたので締めます。 解答くださった方々ありがとうございました。
guest

回答2

0

ベストアンサー

現代のCPUにとって失速の原因はパイプラインストールと呼ばれる分岐予測のミスマッチです。

c

1void bubblesort(int *a, int size) { 2 int i, j; 3 for(i=size-1; i>0; i--) { 4 for(j=0; j<i; j++) { 5#if defined(VERBOSE_MODE) || defined(COUNT_COMPARISON) 6 comparison_counter++; 7#endif 8 if (a[j]>a[j+1]) { 9 swap(a, j, j+1); 10 } 11 } 12 } 13}

この中で分岐はif(){swap(a,j,j+1);}の部分です。
降順の場合、ここは常に分岐するのでパイプラインストールが発生しません。

c

1swap(a, j, a[j]>a[j+1] ? j+1 : j);

と、分岐させない事で同等ないしはランダムのほうが高速化される可能性があるかと思います。

投稿2019/10/21 05:40

asm

総合スコア15147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

asm

2019/10/21 05:57

forも分岐じゃない?とか結局分岐してるのでは?とか面倒くさいけど - 前回の分岐履歴をもとに予測している - 条件jmp + call は分岐予測をミスったときのコストがでかい ようなCPUを使うと起きる現象な気がします
Sugatail

2019/10/21 07:12

解答ありがとうございます。 swapを3項のに換えた結果、 データ40000について:  ランダムデータの実行時間が3129.6(ms)に縮みました。  一方降順データの実行時間は3211.5(ms)に伸びました。 交換回数は共に799980000回です。 どうも降順データが早かった理由ではないようです…。
asm

2019/10/21 07:51

> 同等ないしはランダムのほうが高速化 という予想から外れてませんし想像の範疇です。 swapを呼ぶ・呼ばないの予測を行わない事で、有意に縮みました。 降順データが遅くなる件は詳しいところは分かりませんが2,3ほど予想はできます。 1. ループ内の命令列が複雑化することで長くなってCPUのループ最適化が死んだ 2. 今回使った方法では条件分岐を排除しきれていない 3. 引数が変更される可能性を入れたことで、関数のインライン展開に悪影響を及ぼした。 4. コンパイラが生成する機械語がCPUに対して最適ではない
Sugatail

2019/10/21 09:06

なるほど…ありがとうございます。 それぞれについて調べてみます。
guest

0

「キャッシュ・ラインというのは通常8〜16ワード(ワードはレジスタのビット長)あって、それを一気に読み込みます。従って、1ワード読むと後続(実際は8バイトとか切りの良いアドレスからフィッチします)データもキャッシュに読み込まれます。従って、隣接データをアクセスする時は、ウエイトのかかるメモリをアクセスしないので(データの読み込みの)処理速度が上がります」ため。

投稿2019/10/21 02:45

Sugatail

総合スコア11

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2019/10/21 03:21 編集

バブルソートなので配列ならランダムでも降順でも隣接データになると思います。可能性の話だけで、何の検証もされていません。
Sugatail

2019/10/21 03:22

おh…ホントですね…。 ソース載せますorz
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問