C++ sorting library "Salt"

はじめに

このライブラリは、C++で様々なアルゴリズムのソート関数を汎用的な形で提供することを目的としたライブラリです。テンプレートを利用しているので、型に依存しないソートが可能です。

ダウンロード＆インストール

現在のバージョン: 1.3
更新日時: 2004/08/19

こちらからダウンロードできます。

更新履歴などはreadmeを参照してください。

解凍後、Saltディレクトリをインクルードパスの通った所に置いてください。ビルドなどは特に必要ありません。

イテレータの分類について

このライブラリでは、boost C++ Libraries で定義されているイテレータの分類を利用しています。その分類を以下に示します。

読み書きに関する分類

イテレータに書き込みが可能か、読み込みが可能かなどの基準で分類を行います。以下に示す4種類の分類があります。

分類名	概要
Readable	*演算子によりデータの読み出しが可能
Writable	*演算子によりデータの書き込みが可能
Swappable	std::iter_swap()関数によるイテレータ同士のスワップが可能
Lvalue	*演算子によりvalue_typeへの参照が取得可能

WritableとLvalueとの違いがあまり良く分からないのですが……。 Writableは*it = aの文がコンパイルを通れば良くて、 Lvalueは*itがvalue_typeへの参照を返す必要がある、とboostのページには書いてあります。要するにWritableは、operator=(const value_type&)を持つクラスを返せばいい、ってことなのでしょうか。きっとWritableはstd::ostream_iteratorあたりを意識しているのでしょう。

走査に関する分類

--演算子で後ろに戻ることが可能か、ランダムアクセスが可能かなどの基準で分類を行います。こちらの分類は、それぞれ包含関係にあります。

分類名	概要
Incrementable	++演算子で前方にしか進めず、他のイテレータと位置の比較もできない
Single Pass	++演算子で前方にしか進めず、一度通り過ぎたらもう二度と後方のイテレータは取得できない
Forward Traversal	++演算子で前にしか進めないが、イテレータのコピーをとっておけばもう一度走査しなおすことも可能
Bidirectional Traversal	--演算子を利用して、逆方向に進むことが可能
Random Access Traversal	+演算子や-演算子による移動が定数時間で可能

Incrementableなんか何に使うんだって感じですが、調べてみるとstd::copyのOutput Iterator等はIncrementableに分類されるようです。

簡単な使い方

まずは、基本的な使い方を示します。

001 
002 #include <salt/salt.hpp>
003 #include <iostream>
004 
005 int main(void) {
006   char a[] = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
007   salt::bubble_sort(a, a+52);
008   
009   std::cout << a << std::endl;
010   return 0;
011 }

Saltのすべての関数やクラスなどはsaltネームスペースに定義されています。このプログラムでは、bubble_sort()関数を呼び出してchar型の配列aをソートしています。

bubble_sort()関数の宣言を以下に示します。

001 
002 template<class Iterator>
003 void bubble_sort(Iterator first, Iterator last);
004 
005 template<class Iterator, class Pr>
006 void bubble_sort(Iterator first, Iterator last, Pr comp);

最初の形式は、範囲[first, last)のイテレータに対してバブルソートを行います。要素の比較には、<演算子が使用されます。

二番目の形式は、要素の比較に関数オブジェクトcompを使う点を除いては最初の形式と同じです。

同様の形式で、多くのソート関数が宣言されています。この形式で使用可能な関数の一覧を以下に示します。それぞれの関数の詳細については、適当にWebで検索するなりしてください。山ほどあります。

null_sort(何もしないソート)
stupid_sort(使うな危険)
bubble_sort(バブルソート)
smart_bubble_sort(改良版バブルソート正式名称不明)
shaker_sort(シェーカーソート)
selection_sort(選択ソート)
insertion_sort(挿入ソート)
gnome_sort(ノームソート)
comb_sort(コムソート)
comb11_sort(コムソート11)
shell_sort(シェルソート)
heap_sort(ヒープソート)
merge_sort(マージソート)
quick_sort(クイックソート)

これらのソート関数を「単純ソート」とここでは呼びます。

複合ソート

一部のソートについては、他のソートと組み合わせて使うことが可能です。例を以下に示します。

001 
002 #include <salt/salt.hpp>
003 #include <iostream>
004 
005 int main(void) {
006   char a[] = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
007   salt::b_quick_sort(a, a+52, salt::bubble_sort, salt::boundary<4>());
008   
009   std::cout << a << std::endl;
010   return 0;
011 }

char型配列aを、クイックソートとバブルソートの複合ソートでソートしています。

クイックソートのアルゴリズムの特徴として、ソートする要素を細かく分割していって再帰的にソートするということが挙げられます。その際、要素がある程度細かく分割されたら他のソート方法を使ったほうが高速な場合があります。そのためこの例では、分割された要素の長さが4以下になったらバブルソートを使用するようにしています。

b_quick_sort関数の宣言を以下に示します。

001 
002 template <class Iterator, class Sorter, class Boundary>
003 void b_quick_sort(Iterator first, Iterator last,
004                   Sorter sorter, Boundary boundary);
005 
006 template <class Iterator, class Sorter, class Boundary, class Pr>
007 void b_quick_sort(Iterator first, Iterator last,
008                   Sorter sorter, Boundary boundary,
009                   Pr comp);

最初の形式は、[fisrt, last)の範囲をクイックソートしますが、分割していった部分の長さがBoundary::valueの長さ以下になったらsorterで指定された関数オブジェクトを使用します。また、引数boundaryには、salt名前空間にboundaryというヘルパ構造体が宣言されていますので、上の例のようにして渡してください。

二番目の形式は、要素の比較に関数オブジェクトcompを使う点を除いては最初の形式と同じです。

ほぼ同様の形式で、b_merge_sort関数が宣言されています。

複合ソートのファンクタ

重要:この機能を使うためには、コンパイラがメンバ関数テンプレートをサポートしている必要があります

単純ソート関数と同じシグネチャのファンクタを、複合ソートから作り出すことができます。この機能を利用すれば、複合ソートを何重にも重ねて使用できます(役に立つかどうかは別として)。

001 
002 #include <salt/salt.hpp>
003 #include <iostream>
004 
005 int main(void) {
006   char a[] = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
007   // ファンクタを作成して返す関数
008   salt::b_merge_sort_functor(salt::heap_sort, salt::boundary<4>())
009     // 返ってきたファンクタのoperator()を呼び出している
010     (a, a+52);
011   
012   std::cout << a << std::endl;
013   return 0;
014 }

ここでは返ってきたファンクタから直接にoperator()を呼び出していますが、これをb_quick_sort()の第3引数に渡してやるとちゃんと複合ソートとして動作します。

例で紹介したb_merge_sort_functor()関数の他に、同様の関数b_quick_sort_functor()関数が定義されています。

連続ソート

重要:この機能を使うためには、コンパイラがメンバ関数テンプレートをサポートしている必要があります

複数のソートを順番に実行するファンクタを作成できます。クイックソートにnull_sortを複合してから挿入ソートをしたりするといい感じの速度が出ます。

001 
002 #include <salt/salt.hpp>
003 #include <iostream>
004 
005 int main(void) {
006   char a[] = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
007   // ファンクタを作成して返す関数
008   salt::sequential_sort_functor(
009     salt::b_quick_sort_functor(salt::null_sort, salt::boundary<8>()),
010     salt::insertion_sort)
011     // 返ってきたファンクタのoperator()を呼び出している
012     (a, a+52);
013   
014   std::cout << a << std::endl;
015   return 0;
016 }
017

アドバイス

データの傾向によって、アルゴリズムを使い分けてください…… データ次第ではクイックソートより早くなる場合もあります。例えば、一般にほとんど整列済みのデータに対しては挿入ソートが有効とされています。
私の実装では、ヒープソートとマージソートが何故か比較的に遅いです。使わないほうがいいでしょう。
テストで最も優秀な結果を叩きだしたのは、クイックソートにboundary16～64の挿入ソートを複合した場合でした。ただし、このソートは逆順に並んだデータや同値の多いデータに対しては壊滅的な遅さになりますので状況を選んで。
*_sort()は実は関数ではありません……operator()が定義された構造体のインスタンスです。他のライブラリと一緒に使ってて怪しい挙動になったら注意してみてください。
マージソートはソートする要素群をまるまるコピーできる量のメモリを内部で確保します。
コムソートとコムソート11には、私は速度面での違いを見出せません。
シェルソートの比較間隔には、数列a_n+1=a_n*3+1を使用しています。