マルチキークイックソート（Multikey Quicksort）のための C++ ヘッダ改良版

概要

マルチキークイックソート（Multikey Quicksort）は大量の文字列を整列するのに適した整列手法です．例えば，ランダム順になっている URL 集合や Wikipedia のタイトル集合を整列する場合であれば，単純なクイックソートと比べて 1/2 程度の時間で整列を完了できます．

今回は，以前に作成した C++ ヘッダ（String Sort Library）を再利用しようと考えたものの，思いのほかに使いにくかったので，インタフェースも含めて修正しました．修正版は以下の場所に置いてあります．

mkq-sort.h
- http://sites.google.com/site/headdythehero/cabine/2010/0725/mkq-sort.h?attredirects=0&d=1

基本的な使い方

NULL 文字（'\0'）を終端とする文字列を整列するのが基本的な機能です．整列の対象が std::vector や std::vector であれば，mkq::sort() に begin() と end() を渡すだけで整列できます．

// 文字列のベクタを整列する例です．
std::vector<std::string> strings;

mkq::sort(strings.begin(), strings.end());

// 文字列の配列を整列する例です．
const char **strings;
std::size_t num_strings;

mkq::sort(strings, strings + num_strings);

おまけとして，整数列や実数列の整列にも使えます．特に指定がなければ，数列中の 0 が終端として扱われます．

// 整数列のベクタを整列する例です．
std::vector<const int *> int_arrays;

mkq::sort(int_arrays.begin(), int_arrays.end());

インタフェース

mkq-sort.h が提供するインタフェースは以下のようになっています．

namespace mkq {

template <typename RandomAccessIterator, typename KeyHandler, typename DuplicationHandler>
bool sort(RandomAccessIterator l, RandomAccessIterator r, size_t depth, KeyHandler key_handler,
  DuplicationHandler duplication_handler);

template <typename RandomAccessIterator, typename KeyHandler>
bool sort(RandomAccessIterator l, RandomAccessIterator r, size_t depth, KeyHandler key_handler);

template <typename RandomAccessIterator>
bool sort(RandomAccessIterator l, RandomAccessIterator r, size_t depth);

template <typename RandomAccessIterator>
bool sort(RandomAccessIterator l, RandomAccessIterator r);

}  // namespace mkq

引数の概要

RandomAccessIterator: l, r
- std::sort() の受け取る第一引数，第二引数と同じく，整列対象の範囲を指定します．
std::size_t: depth
- 先頭の何文字をスキップするのかを指定します．
KeyHandler: key_handler
- 文字を取り出す方法と終端の判定方法を指定します．
- デフォルトでは，文字列の operator[] を文字の取り出しに利用し，0 を文字列の終端として扱います．
DuplicationHandler: duplication_handler
- 重複する文字列を見つけたときの動作を指定します．
- デフォルトでは何もしません．

KeyHandler: 文字列の扱い

文字列とインデックスを受け取って文字を返す関数と，文字を受け取って終端かどうかを判定する関数を指定するクラスであり，2 つのオペレータが必要になります．

// UnitType には文字の型，KeyType には文字列の型を指定します．

// key を構成する index 番目の文字を取り出すオペレータです．
UnitType KeyHandler::operator()(const KeyType &key, std::size_t index) const;

// unit が終端文字かどうかを判定するオペレータです．
// 終端文字であれば true，終端文字以外であれば false を返すようにします．
bool KeyHandler::operator()(const UnitType &unit) const;

デフォルトでは以下のようになっています．

// CharToUCharWrapper は char を unsigned char に置き換えるためのクラスです．
// 最上位ビットが 1 になっている char を正の値として処理するようにします．
template <typename T>
class CharToUCharWrapper { public: typedef T Type; };

template <>
class CharToUCharWrapper<char> { public: typedef unsigned char Type; };

template <typename UnitType>
class DefaultKeyHandler
{
public:
  typedef typename CharToUCharWrapper<UnitType>::Type WrappedUnitType;

  template <typename KeyType>
  WrappedUnitType operator()(const KeyType &key, std::size_t index) const
  {
    // 単純に operator[] を使います．
    // KeyType が std::string や const char * であれば，デフォルトのままでも使えます．
    return static_cast<UnitType>(key[index]);
  }

  bool operator()(const WrappedUnitType &unit) const
  {
    // 0 かどうかを終端文字の判定として使います．
    return unit == static_cast<UnitType>(0);
  }
};

一例として，文字列の長さを終端の判定に用いる場合であれば，文字の型を int にして，index が文字列の長さと等しければ -1 を返し，-1 を終端文字として扱うような KeyHandler が考えられます．

DuplicationHandler: 重複する文字列の扱い

整列において重複する文字列が見つかったときに呼び出される関数です．この関数が呼び出された時点で，引数として渡される重複文字列の範囲は，既に整列が完了しています．そのため，以降の整列ではアクセスされないことが保証されます．

整列の後で重複数を求める場合など，無駄な文字列比較を避けたいときは，渡された範囲を NULL や空文字列に置き換えることが可能です．もう少し穏便に，フラグを ON にするというのも可能です．

// true を返せば整列を継続し，false を返せば整列を中止します．
bool DuplicationHandler::operator()(RandomAccessIterator l, RandomAccessIterator r) const;

デフォルトでは以下のようになっています．

class DefaultDuplicationHandler
{
public:
  template <typename RandomAccessIterator>
  bool operator()(RandomAccessIterator l, RandomAccessIterator r) const
  {
    // 何もしません．
    return true;
  }
};

一例として，重複する文字列があるかどうかを調べる場合，false を返すようにしておけば，mkq::sort() の返り値で確認できます．

おまけ

Wikipedia のタイトル（765 万件）と URL のリスト（1000 万件）を整列するのにかかる時間を調べてみました．比較の対象は，標準的なコマンドの sort，およびに std::sort(), mkq::sort() を用いたプログラムです．すべてオンメモリでの整列になっています．

プログラム	タイトル	URL
sort	18.26	33.81
std::sort	16.37	29.65
mkq::sort	7.78	17.45

あらかじめ入力をランダム順に並べ替えておいたので，はっきりと差が出ています．大量の文字列が無作為に並べられている状態からの整列については，マルチキークイックソートの方がクイックソートよりも速いと結論づけても問題なさそうです．ちなみに，ほとんど整列されている状態からの仕上げであれば，どちらを使っても，それほどの差はありません．

使いどころとしては，ハッシュ表（std::unordered_map など）に格納されている文字列を整列する場合などが考えられます．