最近更新したページ
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++ STL nth_element


C/C++ ソート


STL algrithm nth_element

 基本は分類を行う関数(ソートではない)の様である。テスト環境で試してみると想定に反して n番目指定に関係なく全ソートされている様だが、コンパイラの実装により動作が異なってくると思われ、移植性には要注意。

 VC++ で全ソートになるようだが、Turbo C++ でどのように動くか試して見たいと思う...何時か...。
 (Turbo C++ の STL 実装状況がよく判っていない。string の使い方も特殊なようなので心配になってきた)

 ※訂正:VC++ nth_element は全ソートしていません。(少量データはするよう(...に見える...)だが、データ量が大きくなるときっちりソートされてないことを確認。)

ソートテストで使用した関数サンプル

 ※このサンプルは、main_sort.cpp をメインとして分割(分割コンパイル)された一部。
 メイン、ヘッダー、共通関数等は、分割コンパイルの頁を参照。

sort_nth.cpp
※ソートするかどうかはコンパイラ次第。
//#include <iostream>
//#include <time.h>
//#include <string>
#include <vector>
#include <algorithm>
#include <functional>   // プレディケート less<Type>() greater<Type>()
using namespace std;

#include "main_sort.h"

// -----------------------------------------
// ソート関数
// -----------------------------------------

/*****************************
nth_element 1,2
*****************************/
void nth_sort1(vector < int > & v) {             // 参考:0.7210
  dsp_arr(&v[0], (int)v.size());
  // ----------------------------
  nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end());
//nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end(), greater<int>());
  // ----------------------------
  dsp_arr(&v[0], (int)v.size());
}
void nth_sort2(vector < int > & v) {             // 参考:0.7310
  dsp_arr(&v[0], (int)v.size());
  // ----------------------------
  nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end(), asc1_cmp);
//nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end(), des1_cmp);
  // ----------------------------
  dsp_arr(&v[0], (int)v.size());
}
void nth_sort3(vector < int > & v) {             // 参考:0.6010
  dsp_arr(&v[0], (int)v.size());
  // ----------------------------
  nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end(), asc2_cmp());
//nth_element(v.begin(), v.begin()+PARTIAL_SIZE, v.end(), des2_cmp());
  // ----------------------------
  dsp_arr(&v[0], (int)v.size());
}
※ちなみに STL の比較関数等は原則仕様が共通である。
※SIZE 10000, PARTIAL_SIZE 1000, RND_MAX 100 で実行。あれれ partial_sort の同一条件と比較して 約1/4以下で完了? 早いのか?
※訂正:VC++ で nth_element は完全ソートしていないことを確認。早い訳が理解できた。

表示サンプル:elements=10 n=4 昇順
※SIZE 10, PARTIAL_SIZE 4, RND_MAX 100 で実行している。
 41  67  34   0  69  24  78  58  62  64
  0  24  34  41  58  62  64  67  69  78
nth_element1       :       0.0100
  5  45  81  27  61  91  95  42  27  36
  5  27  27  36  42  45  61  81  91  95
nth_element2       :       0.0000
 91   4   2  53  92  82  21  16  18  95
  2   4  16  18  21  53  82  91  92  95
nth_element3       :       0.0100
続行するには何かキーを押してください . . .
※実際には partial sort として動作するらしいが、n番目以前(以降も)ソートされる保証は無く、n番目を境に値の大小を分類(仕分)するものらしい。(※内容非保証)

表示サンプル:elements=10 n=4 降順
 41  67  34   0  69  24  78  58  62  64
  0  24  34  41  58  62  64  67  69  78
nth_element1       :       0.0000
  5  45  81  27  61  91  95  42  27  36
  5  27  27  36  42  45  61  81  91  95
nth_element2       :       0.0100
 91   4   2  53  92  82  21  16  18  95
  2   4  16  18  21  53  82  91  92  95
nth_element3       :       0.0000
続行するには何かキーを押してください . . .
※VC++2005 では、指定 n番に関係なく、全部ソートしているようである。

想定する期待値 n=4 昇順 の場合
元: 41  67  34   0 <-|-> 69  24  78  58  62  64  // n=4 -> "|" が境
後: 34   0  24  41 <-|-> 67  69  78  58  62  64  // 4th を境に分類
※n番目を境とする単なる分類のみと考えておかないと、互換上の問題があるかも。
※この条件に一致すれば処理終了と考えると、手段を選ばず高速(非安定)でが良い?並びの安定性については案外難しいところがあるが、せっかくの STL コードの汎用化的には、パラメータ化されていた方が使いやすい。(早くて、安定で、コンパクトなのが最良…プログラムのアルゴリズムなんて如何でも良いってのが本音。)


▲上へ [ 編集 ]

リンク


内部リンク


外部リンク


  • 現在ありません

▲上へ
2008年07月22日(火) 03:13:10 Modified by cafeboy1




スマートフォン版で見る