soraなりの日々 - fc2 -

こころにひっかかったもの

コードの中心でiをさがす -sort編-


ボス:「ココのこの部分、昇順で並ばせられないかな。」
オレ:「ソートしましょうか。
    (んー、バブル。いやクイックかな。手間だなぁ・・)」

んでも、実際はソースを書くのは約5分で終了。

このエントリーをはてなブックマークに追加







誰でも、なるべくならば容易にものごとを
処理したいと願うものである。
(中略)
なんでもかでも、全力投球さえすれば成功するとはかぎらないのだ。
この際の判断力の良し悪しが、その人の人生がスムーズにいくか、
それとも大変な苦労に満ちたものになるかの、分かれ道であると思う。
 


コレ↓を見て欲しい。







int temp = 0;
for ( int i=0; i<size-1; i++ ) {
    for ( int j=size-1; j>i; j-- ) {
        if ( n[j-1] > n[j] ) {
            temp = n[j-1];
            n[j-1] = n[j];
            n[ j] = temp;
        }
    }
}

なんの変哲もない普通のバブルソートのソース。
今回使ったのは、stlのsort。
因みにこうなる↓







std::sort( nList.begin(), nList.end() );

そう!こんだけ。一行で終わり。
んで、いつもの速度計測。







std::vector<int> nList;

const int size  = 10000;
for ( int iCnt=0; iCnt<size; iCnt++ ) {
    int nRand = rand() % 10000 + 1;
    nList.push_back( nRand );
}

start = clock();

std::sort( nList.begin(), nList.end() );

end = clock();

std::vector<int>::iterator it = nList.begin();
while ( it != nList.end() ) {
    cout << *it << endl;
    it++;
}


結果、、、
...
9997
9999
10000
0.040000秒

バブルソートの場合は、、、
...
9998
9998
10000
121.930000秒

なんだこの差は!バブルだからまー仕方がないか。。。
てことで、最速クイックソート。
...
9996
9997
9999
0.120000秒

おー、おしい!素晴らしくおしい。stlよりクイックのが勝つと思ったんだけどなぁ。
要素増やしたら速度変わるかな。
なので、sizeを1000000に変更した再度計測。

std::sort -> 3.550000秒
quick sort -> 11.360000秒

んー、それでもstd::sortですかい!
なんかこうなるとほんまかいな、と自分のコードを疑ってしまうけど、
(まー、実際、クイックのソース部分は関数分けてあるし、
再帰処理使ってるしで、その分遅くなってるのかも。。)
仮に間違えてたにしろ、処理速度は大して変わりそうにないし、
コード量を考えるとstd::sortのが断然楽!
やっぱ楽しないとね、楽を。


環境:PowerBook G4 1.25 GHz memory 1 GB
  :gcc version 4.0.1 (Apple Computer, Inc. build 5363)
このエントリーをはてなブックマークに追加

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://sora2hs.blog70.fc2.com/tb.php/58-240d1728
この記事にトラックバックする(FC2ブログユーザー)