最近更新したページ
2013-10-20
2013-09-29
2013-09-23
2012-01-07
2011-11-09
2011-10-23
2011-10-09
2011-10-01
2011-09-29
2011-09-03
2011-08-07
2011-08-02
2011-07-29
2011-07-10
2011-05-05
2011-05-04
2011-04-24
2011-04-13
2011-04-05
2011-03-26
2011-02-18
2011-02-15
2010-12-26
2010-12-07
2010-12-05
2010-11-23
2010-09-28
2010-09-23
2010-08-26
2010-08-22
2010-07-16
2010-01-17
2010-01-11
2009-10-04
2009-08-21
2009-08-13
2009-06-18
2009-06-01
2009-04-29
2009-02-16
2009-02-11
2009-02-03
2008-07-22
2008-07-21
2008-07-15
2008-07-14
2008-07-13
2008-07-12
2008-07-08
2008-07-05
2008-06-28
2008-06-17
2008-06-05
2008-06-02
2008-06-01
2008-05-29
2008-05-26
2008-05-21
2008-05-19
2008-05-18
2007-10-31
2007-10-27
2007-09-28
2007-09-23
2007-09-17
2007-09-16
2007-09-14
2007-09-11
2007-06-18
2007-04-15
2006-12-21
2006-11-30
2006-11-22
2006-08-17
2006-03-29
2006-03-28
2006-03-27

C/C++ その他のソート


C/C++ ソート


STL その他のソート

 qsort STL のソートと比べ速度低下を懸念していたが、汲み方で非常に高速に処理されることを確認。
 qsort が早い理由は、おそらく内部でポインタを利用している為と思われる。
 STL で速度が思うほど出ない理由としては、イテレータで処理されている為では無いか?と思われる。ポインタ同等と思われたイテレータだが、高機能な反面、利用上の制限や処理ステップが多分多いのでは無いか?
 最後に、別途関数として準備したバブルソートでも、ポインタを利用し、スワップをインラインで記述すれば相当高速に動作することが判ったのは、非常に大きな収穫である。

バブルソート

 動作未確認サンプル。(コンパイルのみ確認。動作未確認。)
 安定したソートを提供。実行速度は遅めと思われる。

sub_sort_bub.cpp
※バブルソートの雛型のようなソースコード。
※このまま実行すると、非常に遅いのだが...?(メマイするほど遅い…)
※メモリも"ばか"食いしてる?
※不具合修正済み
#include <iostream>
//#include <time.h>
//#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#include "main_sort.h"

/****************
buble sort
*****************/
void o02_sort(vector < int > & v) {

   const int size = (int)(v.size());
   dsp_arr(&v[0], size);                  // 表示確認用

   int temp = 0;

   for (int i=0; i < size-1; i++) {
      for (int j=size-1; j > i; j--) {
         if ( v[j-1] > v[j] ) {          // ">":昇順 "<":降順
            temp   = v[j];                // 参考値:220.5400
            v[j]   = v[j-1];
            v[j-1] = temp;
         }
      }
   }
   dsp_arr(&v[0], size);
}
※swap 関数を使った方が実行が早い模様。未汎用化。イテレータで工夫するともっと早いかも。
※注:後で追加したので、メイン、ヘッダーへ追加されてない。

※上記バブルソートで正しく並べ替えされてないことが発覚、再確認中。
※昇順・降順・動作チェック実施。

sub_sort_bub.cpp ポインタ使用の修正版
※不具合修正版
〜 省略 〜
/****************
buble sort
*****************/
void o02_sort_fn(int* p, const int size) {

   dsp_arr(p, size);                      // 配列要素確認用

   int temp = 0;
   for (int i=0; i < size-1; i++) {
      //cout << i ;
      for (int j=size-1; j > i; j--) {
      //cout << j;
         if ( *(p+j-1) > *(p+j) ) {       // ">":昇順 "<":降順
            //swap( *(p+j), *(p+(j-1)) ); // 参考値:9.9040
            temp       = *(p+j);          // インライン化が断然早い。
            *(p+j)     = *(p+(j-1));      // 参考値:2.3630
            *(p+(j-1)) = temp;
         }
      }
      //cout << endl;
   }
   dsp_arr(p, size);
}
void o02_sort(vector < int > & v) {
   o02_sort_fn(&v[0], (int)v.size());
}
※劇的に高速になった。(sub_sort_o01.cpp より約3倍早い。)
※インラインでスワップさせたところより高速に動作することを確認。ポインタ利用でこれほど処理速度に影響するとは思わなかった。

※上記バブルソートで正しく並べ替えされてないことが発覚、再確認中。
※昇順・降順・動作チェック実施。


▲上へ [ 編集 ]

?ソート

 このアルゴリズムに似たコードで基数ソートと呼ばれるものがあるが、これは異なる。
 基数ソートは、各桁を取り出してまず並べ替えると言った処理を行う。(最大桁数が大きいとループ回数が増える?但しスキップされるループも多いと思われるが...安定ソートでもある。)

sub_sort_o01.cpp
※これも多分バブルソートに近い???と思われる。(安定ソート確認済み)
※ポインタを使っているため???か、sub_sort_bub.cpp より遥かに高速。
//#include <iostream>
//#include <time.h>
//#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#include "main_sort.h"
// o01_sort 比較関数 昇順・降順
int asc_cmp(const void* a, const void * b) {     // 昇順用
   return *(int *)a - *(int *)b;
}
int des_cmp(const void* a, const void * b) {     // 降順用
   return *(int *)b - *(int *)a;
}
// swap sub
void x01_swap_fn(int* x, int* y) {
   int temp = *x;
   *x = *y;
   *y = temp;
}
// sort関数(function)
void x01_sort_fn(int* p, int size,
                 int (*p_cp)(const void* x, const void* y) ) {

   dsp_arr(p, size);
   int temp;

   int end_pos = size;
   while ( end_pos >= 0 ) {
      int left_pos=-1, right_pos=1;

      for( ; right_pos < end_pos; right_pos++) {      // "<="を"<" 修正
         left_pos = right_pos-1;

         if ( p_cp( p+left_pos, p+right_pos ) > 0 ) { // 比較関数呼出
            //swap(*(p+right_pos), *(p+left_pos));    // 参考値:14.5410
            //x01_swap_fn(p+right_pos, p+left_pos);   // 参考値:13.6690
            temp           = *(p+right_pos);          // 参考値: 9.2530
            *(p+right_pos) = *(p+left_pos);
            *(p+left_pos)  = temp;
         }
      }
      end_pos = left_pos;
   }
   dsp_arr(p, size);
}
// このファイルのメイン関数
void o01_sort(vector < int > & v) {
   x01_sort_fn(&v[0], (int)(v.size()), asc_cmp);
}
※他の頁(たしか「構造体とソート」の頁?)から単一データ仕様へ修正して使えるようにした関数。
※比較関数は、構造体ソート用を単一データ用へ修正。qsort の比較関数と互換なので代用可。
※swap 関数は、標準の swap 関数でも良い。動作的には 関数とせずインライン化すべき(これを関数にする意味は無い。この場所はオーバーヘッド要因を極力排除すべき場所(※最適化で速度を左右))と思うが面倒なのでそのまま利用。

※降順は問題なし。昇順で実行時エラー
※せっかく qsort と比較関数を合せてみたが、これを使って昇順・降順をコントロールすることが出来ない。何故?比較対照を比較関数でのすげ替えは可能と思われる。
※昇順・降順・動作チェック実施。


▲上へ [ 編集 ]

リンク


内部リンク


外部リンク


  • 現在ありません


▲上へ [ 編集 ]
2008年07月21日(月) 13:12:13 Modified by cafeboy1




スマートフォン版で見る