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 コードの汎用化的には、パラメータ化されていた方が使いやすい。(早くて、安定で、コンパクトなのが最良…プログラムのアルゴリズムなんて如何でも良いってのが本音。)
▲上へ [ 編集 ]
リンク
内部リンク
- C/C++ C++/CLI C# 関連
- VC++ 2005 Express のインストール
- C/C++ の簡単なプログラム例
- C/C++ ソート(並べ替え)
- C/C++ テストの実行
- C/C++ STL(Standard Template Library)
- 変数・定数
- プログラムの分割/ダイナミックリンクライブラリ など
- その他
- C/C++ その他::書式文字/ESC code など
- VB2005リファレンス(覚え書き)
- SQL文:SQLステートメント
- VBA(VisualBasic for Applications)
外部リンク
- 現在ありません
▲上へ
2008年07月22日(火) 03:13:10 Modified by cafeboy1