ソート時間について（関連：連結リスト　その２）

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
れお
記事: 113
登録日時: 13年前

ソート時間について（関連：連結リスト　その２）

#1

投稿記事 by れお » 13年前

昇順にソートします。

コード: 

#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* Listsort(SRec *node,int (*comp)(const void *,const void *))
{
    SRec head; //ソート前リスト
    SRec top;  //ソート後リスト

    head.next = node;  // head.next はソート前のリストへのポインタ
    top.next = NULL;  // top.next はソート後のリストへのポインタ

    while (head.next != NULL) {  // head が空になるまで繰り返す
                SRec *save1 = &head;        // 現在の最大値の一つ前を指す
                SRec *save2 = head.next;    // 先頭要素を現在の最大値とする
                SRec *p;                     // head を順に見ていくポインタ
                for (p = &head; p->next != NULL; p = p->next) {
                    if (comp(p->next, save2) > 0) {  // 現在の最大値と比較
                        save1 = p;           // 新しい最大値の一つ前を指す
                        save2 = p->next;     // 新しい最大値を指す
                    }
                }
                save1->next = save2->next; // save2 を head から削除
                save2->next = top.next;    // save2 を top の先頭に挿入
                top.next = save2;          // save2 を top の先頭に挿入
            }
            return top.next;  // ソート後のリストへのポインタを返す
        }


int compare_gpa(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1;                         //これは - ではできない∵int
}
int compare_credit(const void* a, const void* b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}

int compare_name(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}

SRec* Input(FILE* fpi)
{
    SRec head;           //入力データのリスト
    SRec *node=NULL;    //データを読み込むノード
    head.next = NULL;/*これが NULL だとリストにはまだ 1つもノードがないことを表す。
                       これが NULL でないとリストに最低 1つはノードがあることになる。
                       実際にはまだリストは空っぽだから NULL する。*/
    while (1)
    {
        node = (SRec *) malloc(sizeof(SRec));//これは配列ではない
        if (node == NULL)
        {
            fprintf(stderr,"メモリ不足");
            return NULL;
        }
        if (fscanf(fpi, "%f%d%s", &node->gpa, &node->credit, node->name) != 3)
        {
            break;  // 読み込みに失敗したら EOF (feof は使わないほうがよい)
        }
        node->next=head.next;
        head.next=node;
    }
    free(node);
    return head.next;  // リストの先頭要素へのポインタを返す。
}
void Output(SRec *node, FILE* fpo)
{
    SRec* list;
    for (list=node; list != NULL; list = list->next)
        fprintf(fpo,"%3.1f %d %s\n", list->gpa, list->credit, list->name);
}
void Free(SRec* node)
{
    SRec *list,*next;
    for(list=node;list != NULL;list = next)
    {
        next=list->next;
        free(list);
    }
}
int main(int argc, char *argv[])
{
    SRec *node=NULL;
    FILE *fpi, *fpo;
    clock_t clk_start, clk_end;
    int (*comp)(const void*,const void*);//比較関数へのポインタ
    if (argc != 4)
    {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL)
    {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL)
    {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp=compare_gpa;//&はどちらでもいい
    else if (strcmp(argv[1], "credit") == 0)
        comp=compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp=compare_name;
    node = Input(fpi);
    if (node == NULL) return 1;
    clk_start = clock();
    node=Listsort(node,comp);
    clk_end = clock();
    printf("%f",(double)(clk_end - clk_start) / CLOCKS_PER_SEC);
    Output(node, fpo);
    Free(node);
    fclose(fpi);
    fclose(fpo);
    return 0;
}
上記のコードで、ソートする関数であるListsortにかかる時間を計測しました。

コード: 

    clk_start = clock();
    node=Listsort(node,comp);
    clk_end = clock();
というふうに。

入力ファイルは
gpa（小数）　credit（整数）　name(英数字)
gpa credit name
・
・
・
という風にはいっています。
コマンドラインは　name input.txt output.txtというふうになっていて、name　について昇順に並べ替えます

ソートにかかった時間は

データ数　　未ソート　ソート済
------------------------------
100000個 621.04秒 425.95秒
80000秒 333.24秒 242.18秒
60000個　 201.06秒 131.5秒
50000個　 143.98秒　109.01秒
40000個　 107.53秒 52.83秒
30000個　 58.76秒 36.51秒
20000個 11.45秒　 6.71秒
10000個　 3.81秒　　1.57秒
（ソート済みとは、ソートしたやつを入力ファイルにして再度ソートしなおしたときのことです）

となりました。

人によってはソート済みのものをソートしたほうが時間がかかってる人もいました。
自分的には、データがばらばらにならんでいるものをソートするときは、
最初の２つのデータで大きいほうを覚える→覚えた大きい方と、３つめのデータをくらべ大きいほうを保存する→覚えたやつと４つめを比較して大きいほうをおぼえる→・・・・
となっていくので、覚えた大きいものが最大だったとするとそのあとは覚えるという作業をせずにすむので、未ソートのほうがソートの時間がかからないように思えるのですがどうなんでしょうか？

ちょっとわかりにくかったかもしれませんので、ソート済みのほうを再度ソートするほうについても言うと、ソート済みということは
最初の２つを比べて大きい方である２つめを覚える→覚えたやつと３つめを比べて、大きい方は３つめなので３つ目を覚える→４つ目をおぼえる→５つ目・・・
というふうに毎回覚えている大きい方がかわっていくので、その分時間がかかるような気がするのです。つまりデータの入れ替え回数が多いのではないかということです。

比較回数はO(n＾2)、データの入れ替え回数はO(n)なので、比較回数はどっちも同じだろうしやはりデータの入れ替え回数が多いソート済みのほうが時間かかる気がするのですが・・・
どうなってるのでしょうか？


なにか上記でよくわからないことあったら言ってくださいm(__)m
最後に編集したユーザー れお on 2012年6月23日(土) 14:51 [ 編集 1 回目 ]
ページトップ
かずま

Re: 成績データのソートにかかる時間について（関連：連結リスト　その２）

#2

投稿記事 by かずま » 13年前

れお さんが書きました:比較回数はO(n＾2)、データの入れ替え回数はO(n)なので、比較回数はどっちも同じだろうしやはりデータの入れ替え回数が多いソート済みのほうが時間かかる気がするのですが・・・
どうなってるのでしょうか？
そのプログラムでは、Input で作ったリストが逆順になりますから、
Sortlist では、リストの先頭の最大値を更新することがなくなり、高速になっています。
ページトップ
れお
記事: 113
登録日時: 13年前

Re: ソート時間について（関連：連結リスト　その２）

#3

投稿記事 by れお » 13年前

あっそうでした！！ありがとうございます。。
ページトップ
かずま

Re: ソート時間について（関連：連結リスト　その２）

#4

投稿記事 by かずま » 13年前

ノードをいくつか連結して 1 つのリストになります。
SRec 構造体が 1つのノードです。
SRec * はノードへのポインタですが、 リストの先頭要素であるノードへの
ポインタは、リストへのポインタといっていいでしょう。

れおさんのプログラムでは、SRec *node と SRec *list のほとんどが反対です。

さて、ソート時間についてですが、コンパイルには最適化のオプションをつけていますか？

また、C ではなく C++ だったら、list が使えますから、次のプログラムの時間を計ってみてください。

コード: 

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <list>
#include <ctime>
 
using namespace std;

struct SRec { float gpa; int credit; string name; };
 
bool comp_gpa(const SRec& a, const SRec& b)    { return a.gpa < b.gpa; }
bool comp_credit(const SRec& a, const SRec& b) { return a.credit < b.credit; }
bool comp_name(const SRec& a, const SRec& b)   { return a.name < b.name; }

int main(int argc, char *argv[])
{
    if (argc != 4) { cerr << "Illegal number of argument.\n"; return 1; }

    ifstream ifs(argv[2]);
    if (!ifs) { cerr << "Can't open input file <" << argv[2] << ">.\n"; return 1; }

    ofstream ofs(argv[3]);
    if (!ofs) { cerr << "Can't open output file <"  << argv[3] << ">.\n"; return 1; }

    bool (*comp)(const SRec&, const SRec&);
    string key = argv[1];
    if (key == "gpa")
        comp = comp_gpa;
    else if (key == "credit")
        comp = comp_credit;
    else if (key == "name")
        comp = comp_name;
    else { cerr << "key must be gpa, credit, or name\n"; return 1; }

    list<SRec> listSRec;  SRec node;

    while (ifs >> node.gpa >> node.credit >> node.name)  // node に読み込み
        listSRec.push_back(node);                        // listSRec に追加

    clock_t clk_start = clock();
    listSRec.sort(comp);
    clock_t clk_end = clock();
    cout << double(clk_end - clk_start) / CLOCKS_PER_SEC << endl;

    ofs.setf(ios::fixed, ios::floatfield);
    ofs.precision(1);   // "%.1f"
    for (list<SRec>::iterator it = listSRec.begin(); it != listSRec.end(); ++it)
        ofs << setw(6) << it->gpa << setw(4) << it->credit
            << "  " << it->name << endl;
}
ページトップ
れお
記事: 113
登録日時: 13年前

Re: ソート時間について（関連：連結リスト　その２）

#5

投稿記事 by れお » 13年前

かずま さんが書きました:ノードをいくつか連結して 1 つのリストになります。
SRec 構造体が 1つのノードです。
SRec * はノードへのポインタですが、 リストの先頭要素であるノードへの
ポインタは、リストへのポインタといっていいでしょう。

れおさんのプログラムでは、SRec *node と SRec *list のほとんどが反対です。

さて、ソート時間についてですが、コンパイルには最適化のオプションをつけていますか？

また、C ではなく C++ だったら、list が使えますから、次のプログラムの時間を計ってみてください。

コード: 

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <list>
#include <ctime>
 
using namespace std;

struct SRec { float gpa; int credit; string name; };
 
bool comp_gpa(const SRec& a, const SRec& b)    { return a.gpa < b.gpa; }
bool comp_credit(const SRec& a, const SRec& b) { return a.credit < b.credit; }
bool comp_name(const SRec& a, const SRec& b)   { return a.name < b.name; }

int main(int argc, char *argv[])
{
    if (argc != 4) { cerr << "Illegal number of argument.\n"; return 1; }

    ifstream ifs(argv[2]);
    if (!ifs) { cerr << "Can't open input file <" << argv[2] << ">.\n"; return 1; }

    ofstream ofs(argv[3]);
    if (!ofs) { cerr << "Can't open output file <"  << argv[3] << ">.\n"; return 1; }

    bool (*comp)(const SRec&, const SRec&);
    string key = argv[1];
    if (key == "gpa")
        comp = comp_gpa;
    else if (key == "credit")
        comp = comp_credit;
    else if (key == "name")
        comp = comp_name;
    else { cerr << "key must be gpa, credit, or name\n"; return 1; }

    list<SRec> listSRec;  SRec node;

    while (ifs >> node.gpa >> node.credit >> node.name)  // node に読み込み
        listSRec.push_back(node);                        // listSRec に追加

    clock_t clk_start = clock();
    listSRec.sort(comp);
    clock_t clk_end = clock();
    cout << double(clk_end - clk_start) / CLOCKS_PER_SEC << endl;

    ofs.setf(ios::fixed, ios::floatfield);
    ofs.precision(1);   // "%.1f"
    for (list<SRec>::iterator it = listSRec.begin(); it != listSRec.end(); ++it)
        ofs << setw(6) << it->gpa << setw(4) << it->credit
            << "  " << it->name << endl;
}

なるほど。ノード＝リストだと思ってました。m(__)m

最適化のオプションってなんですか？eclipsなんで、コンパイルとビルドを一気にやってしまうしコンパイルとか意識したこともないです＾＾；

プログラムがなにやってるかわかりません・・・コマンドライン引数はどんなかんじですか？？；
ページトップ
かずま

Re: ソート時間について（関連：連結リスト　その２）

#6

投稿記事 by かずま » 13年前

れお さんが書きました: 最適化のオプションってなんですか？eclipsなんで、コンパイルとビルドを一気にやってしまうしコンパイルとか意識したこともないです＾＾；

プログラムがなにやってるかわかりません・・・コマンドライン引数はどんなかんじですか？？；
eclipse ですか？
Windows で cygwin gcc を使っているんでしょうか？　それとも、Linux？

私も eclipse は詳しくないんですが、次のことを試してみてください。

Project Explorer で、プロジェクト名を右クリックし、一番下の Properties をクリック。
左の C/C++ Build の + をクリックし、表示された中の Settings をクリック。
右の Configuration: が Debug [ Active ] になっているのを Release に切り替える。
さらに右の Manage Configurations をクリックっし、Release を選んで、Set Active, OK。
その下の Tool Settings で、GCC C++ Compiler に対して、右の Command: は g++,
All Options: は -O3 で始まっているはず。この -O3 が最適化のオプションです。

Configuration: が Debug のときは、All Options: は -O0 で最適化なしになっていたはず。

コマンドライン引数は、一番左の Run/Debug Settings をクリックし、表示されたプロジェクト名を選択し、
右の Edit をクリックすると、Main タブの C/C++ Application: には Relase/<プロジェクト名> と
表示されているはず。
Arguments: タブの　Program Arguments: に gpa a.txt b.txt を入れる。
ページトップ
れお
記事: 113
登録日時: 13年前

Re: ソート時間について（関連：連結リスト　その２）

#7

投稿記事 by れお » 13年前

windowsですでもプロジェクトエクスプローラーからもう何なのかわかってないです＞＜
すみません・・・でも今回は他の人と同一のハードウェア仕様かつ同一の使用環境のもとでの計測なのでそういうところはいじらなくていいのかもしれません。
それで何ができるのかわからないのでかみ合ってないかもしれませんが。。。＾＾；
話は少しかわって？自分が今回しりたいのは
?? データ数を増やすと処理時間はどのように増加
するか？
?? 理論と実際の差異はどうか？
ということなんですが、理論値が計算量などをつかって出せずに詰まってます??ランダムデータの場合： 比較＋ 入れ替え
?? ソート済みデータの場合： 比較のみ
（上以外に時間に差が生じた要因はないですよね？ないはず・・・）
なのでソート済みの時間を見ればそれが比較にかかった時間ということになるはず！（入れ替えは必ずしも毎回おこなわれないので参考にならない）

∴比較分のO(ｎ＾２)を利用して、データ数が１万の時ソート済みは１．５７秒かかったので、データ数が２万の時はデータ数が２倍になったので２＾２＝４、つまり４倍の時間がかかるから２万個の時のデータ済みのソート時間は６秒でまぁほぼ実験値とあっているのですが、このやり方だとこれ以降がもうあわなくて、間違ってるようです・・・この考え方はなにがだめなのでしょう・・・
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る