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

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

ただいまの
回答率

90.50%

  • C

    3692questions

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

  • ソート

    67questions

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

未ソートデータとソート済データをソートプログラムに入れた場合の、実行にかかる時間の比較

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 219

zazenbo

score 2

 解決したい疑問点

環境は、Windows7, eclipse を使っています。

一方向連結リストをソートするプログラムに、未ソートデータとソート済データを入力した場合について、プログラムの実行時間を比較したところ、未ソートデータのほうが時間がかかったのですが、なぜそうなるのかがわかりません。

下記ソースコードの概要は、
・gpa,credit,name の3要素から構成される生徒の成績データが、input.txtファイルに
....................
3.5 40 Taro
2.1 60 Hanako
.
.
....................
のような形で数万人分記録されていて、それを input 関数で構造体の連結リストに入力する。
・input.txtファイルとoutput.txtファイルの場所はコマンドライン引数で入力。
・gpa,credit,name のいずれでソートするかもコマンドライン引数で入力。今回は name でソート。
・ソートは昇順。最大値抽出法を使用。
・ソート部分の実行時間を知るため、sort 関数を clock 関数で囲んでいる。
・入力データには、バラバラの未ソートデータおよび、すでにソート済のデータの2つを使用し、比較する。

 該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct school_record SRec;
struct school_record{
    float gpa;
    int credit;
    char name[200];
    SRec *next;
};

SRec* input(SRec* p, char* fname1);
void output(SRec* p, char* fname2);
int gpa_comp(const void* val1, const void* val2);
int credit_comp(const void* val1, const void* val2);
int name_comp(const void* val1, const void* val2);
SRec* listsort(SRec* header, int (*comp)(const void*, const void*));
SRec* sort(SRec* header, char* key);



int main(int argc, char *argv[])
{
    SRec* header = NULL, *Sheader;
    clock_t clk_start, clk_end;

    // コマンドライン引数チェック
    if(argc != 4){
        fputs("コマンドライン引数の数が間違っています.\n", stderr);
        exit(0);
    }
    if(strcmp(argv[1],"gpa") && strcmp(argv[1],"credit") && strcmp(argv[1],"name")){
        fputs("1つめのコマンドライン引数は, gpa, credit, name のいずれかにしてください.\n", stderr);
        exit(0);
    }

    header = input(header, argv[2]);

    clk_start = clock(); // sort関数の処理時間を計測
    Sheader = sort(header, argv[1]);
    clk_end = clock();

    output(Sheader, argv[3]);

    printf("%f", (double)(clk_end - clk_start) / CLOCKS_PER_SEC);

    return 0;
}




SRec* input(SRec* header, char* fname1)
{
    float gpa;
    int credit;
    char name[200];
    SRec *p;
    SRec **tail = &header;

    // ファイルのオープン
    FILE *fp;
    if ((fp = fopen(fname1, "r")) == NULL){
        fprintf(stderr, "%sのオープンに失敗しました.\n", fname1);
        exit(1);
    }

    // データをリストへコピー
    while( fscanf(fp, "%f%d%s", &gpa, &credit, name) != EOF){

        // 領域確保
        if( (p = (SRec*)malloc(sizeof(SRec)) ) == NULL){
            fprintf(stderr, "データ領域の確保に失敗しました.\n");
            exit(1);
        }
        // 一時変数からリストへ書き込み
        p->gpa = gpa;
        p->credit = credit;
        strcpy(p->name, name);
        p->next = NULL;

        // リストの末尾に要素を追加 (tail は header か next を指すポインタ)
        *tail = p;
        tail = &(p->next);
    }
    fclose(fp);
    return header;
}



void output(SRec* p, char* fname2)
{
    SRec* tmp;

    // ファイルのオープン
    FILE *fp;
    if ((fp = fopen(fname2, "w")) == NULL){
        fprintf(stderr, "%sのオープンに失敗しました.\n", fname2);
        exit(1);
    }
    // データの書き込み
    while( p != NULL ){
        fprintf(fp, "%.1f %3d %s\n", p->gpa, p->credit, p->name);
        tmp = p;
        p = p->next;
        free(tmp);
    }
    fclose(fp);
}






// gpa比較関数
int gpa_comp(const void* val1, const void* val2)
{
    return ( (*(SRec*)val1).gpa < (*(SRec*)val2).gpa ) ? -1 : ( (*(SRec*)val1).gpa == (*(SRec*)val2).gpa ) ? 0 : 1 ;
}

// credit比較関数
int credit_comp(const void* val1, const void* val2)
{
    return ( (*(SRec*)val1).credit < (*(SRec*)val2).credit ) ? -1 : ( (*(SRec*)val1).credit == (*(SRec*)val2).credit ) ? 0 : 1 ;
}

// name比較関数
int name_comp(const void* val1, const void* val2)
{
    return strcmp( (*(SRec*)val1).name, (*(SRec*)val2).name);
}



// ソートを行う関数
SRec* listsort(SRec* header, int (*comp)(const void*, const void*))
{
    SRec* Sheader = NULL, *q;
    SRec** p, **max;  //header か next を指すポインタ

    // 元リストが空になるまで以下を繰り返し
    while( header != NULL ){
        p = &header, max = &header;

        // 元リストの最大値を探す
        while( *p != NULL ){
            if( comp(*max, *p) < 0 ){
                max = p;
            }
            p = &( (*p)->next );
        }
        // 元リストの最大値を削除して、新リストの先頭に挿入
        q = Sheader;
        Sheader = *max;
        *max = (*max)->next;  // 削除完了
        Sheader->next = q;    // 挿入完了
    }
    return Sheader;
}


// keyに対応する比較関数をlistsort関数へ振り分ける
SRec* sort(SRec* header, char* key)
{
    SRec* Sheader = NULL;

    if(strcmp(key, "gpa") == 0){
        Sheader = listsort(header, gpa_comp);
    }
    if(strcmp(key, "credit") == 0){
        Sheader = listsort(header, credit_comp);
    }
    if(strcmp(key, "name") == 0){
        Sheader = listsort(header, name_comp);
    }

    return Sheader;
}

 結果

入力データ
データ数   未ソート   ソート済
.............................................
10000個   0.70秒   0.76秒
20000個   3.02秒   2.91秒
40000個   13.58秒  12.96秒
50000個   24.72秒   21.22秒
60000個   41.66秒   34.53秒
80000個   86.76秒    68.59秒
100000個   147.48秒  111.96秒
..............................................

となりました。ソートは問題なく行われます。
データ数が多くなると、ソート済データのほうが実行時間がかなり早いです。

 なぜなのか

listsort 関数内に関して、ループを回す回数は未ソートとソート済で変わらないはずです。未ソートとソート済で違うところがあるとすれば、それは

// 元リストの最大値を探す
        while( *p != NULL ){
            if( comp(*max, *p) < 0 ){
                max = p;
            }
            p = &( (*p)->next );
        }


のif文が、未ソートの場合は実行される時とされない時があり、ソート済の場合は毎回実行される、ということだと思います。
ですから、むしろソート済のほうが実行時間が長くなるはずだと思うのですが・・・

なぜ未ソートのほうが時間がかかるのか、教えてください。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+4

結論から言うと、データの局所性の影響によるものだと考えられます。

まず、アセンブルリストを出力してどのようにコンパイルされたのかを確認したところ、比較部分でcmovsを使っていたので、ソート済みとソートなしとではまったく同じパスが実行される、つまり、その部分では速度に差が出ないということが判りました。

となると、考えられるのはデータの局所性の影響です。1要素のサイズが216バイト(64bit環境の場合)で、1万件だと2,160,000バイト、つまり、2MBちょっとということで、そこそこ大きいです。実際にはヒープの管理領域も含まれるのでそれよりも若干大きくなるでしょう。とはいえ、デスクトップ向けのCPUなら十分キャッシュに収まります。2万件だと4MB超。CPUのモデルによってはそろそろ収まりきれないかもしれません。4万件だと8MB超。ハイエンド向けのCPUでもキャッシュから溢れます。
キャッシュから溢れた場合は、次にそのデータを読むときはシステムメモリ(DRAM)から読み出すことになりますが、その際、プリフェッチという仕組みが働き、ある程度まとまったサイズの連続した領域を「先読み」します。先読みした領域はキャッシュに保存されるので、DRAMよりも遥かに高速に読み書きできます。

ここで「局所性」が効いてくるわけです。順番がバラバラだと、先読みした領域に次に使いたいデータが存在する確率は低いですが、順番が整っている(ソート済みの)データだと、次に使いたいデータが先読みした領域に存在する可能性は極めて高くなります。
キャッシュが有効に働くというわけです。

ソート済みのデータの方が実行時間が短いのは、そして、件数が多いほどより顕著に表れるのはそのためではないかと思われます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/27 12:35

    初学者ゆえ知らないことだらけでしたが、わかりやすい説明のおかげで理解することができました。
    他の方もわかりやすかったのですが、最も詳しい説明だったのでベストアンサーにさせて頂きます。

    回答ありがとうございました!

    キャンセル

+2

未検証なので自信はないのですが、「参照の局所性」とか呼ばれたりする現象ではないかと思います。
ソート済みの方がメモリアクセスする範囲が集中しますので、メモリのキャッシュが有効に働いて効率的になるからではないかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/27 16:17

    「参照の局所性」、知らなかったですが、たしかに影響していそうですね。

    回答ありがとうございました!

    キャンセル

+2

コンパイラ・CPUの仕様によりますが
アセンブリ言語レベルですと
CPUの高速化(パイプライン)の都合で条件分岐の予測をCPUが間違えると遅くなります。

ループ内の条件分岐ですので、CPUが前回の分岐と同方向を予測するアルゴリズム
もしくは、常に分岐すると予測するアルゴリズムであった場合
ソート済みか否かで速度が変わる要因になります。


なんとなくですが、三項演算子を用いる事でcmov命令に最適化されそうな気がします。

max = comp(*max, *p) < 0 ? p : max;

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/27 16:14

    CPUが効率的に処理してくれるから本来の時間計算量以上の性能が出たわけですね。

    三項演算子は試してみましたが、結果は同じでした…。

    回答ありがとうございました!

    キャンセル

0

ソート時と未ソート時ではcomp関数の実行時間が違うからでは

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/27 16:23

    comp関数の実行時間、実質的には strcmp 関数の実行時間ということですかね?
    未ソートとソート済で実行時間が変わる理由が思いつかないです…

    キャンセル

  • 2018/06/27 16:34

    まあ、ソート済みであれば常に最小の文字比較で終わるけど、ソートされてなければ、(それに比べ)長い文字の比較となるってとこですな。
    strcmp関数を自分で実装するとなるとどういうふうに組むか、を考えるとわかると思います

    キャンセル

  • 2018/06/28 01:13

    たとえば未ソートなら
    taro と hanako
    のような比較が多く、ソート済なら
    tarao と taro
    のような比較が多くなると思います。
    strcmp関数では文字列の1文字目から順に大きさを比較し、大きさが違う文字があった時点でreturnするので、未ソートの taro と hanako では1文字目でreturn、ソート済の tarao と taro では4文字目でreturnとなると思います。ですからその意味でもやはり、未ソートのほうが早く終わるように思えてしまうのですが・・・

    キャンセル

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

  • ただいまの回答率 90.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    3692questions

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

  • ソート

    67questions

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

  • トップ
  • Cに関する質問
  • 未ソートデータとソート済データをソートプログラムに入れた場合の、実行にかかる時間の比較