はじめに
この記事の目的は、「C++のSTLにはデータをソートする方法がいくつか存在するが、ソート処理を簡単に、かつ効率のよいコードはどれか…」を調べることです。
ここでは、自前のソートアルゴリズムを作って速度を比較したり、既存のソートアルゴリズムを最適化するといったことは目的としません。公開されているSTLをありのままの姿で計測します。コードの保守性や移植性、可読性を考慮して「いたって普通」な書き方が一番メリットが受けられると考えていますし、より多くの人に恩恵をもたらすと考えるからです。
自前のソートアルゴリズムの構築や、既存のアルゴリズムの最適化は、可読性や移植性を悪くするため、得られるメリット（高速処理による時間）よりもデメリットが大きいと考えているのです。よって、ここで検証するコードは「いたって普通」な書き方であり、可読性を重視した書き方になります。
自前でソートアルゴリズムの構築をして既存のアルゴリズムと競わせてみたいと思う方は、ここのソースコードを元に各自で計測してみるとよいでしょう。
対象読者
C++でSTLを使っている人。C++でSTLを使い始めた人。
開発環境
筆者の環境は、VC++ 2005 EEです。最初は、使い慣れたVC++ 6.0で書いていたのですが、list::sort（*1）に問題があり、VC++ 2005 EEがフリーで公開された（*2）こともあって、最新の環境に移行しました。
動作の確認は、Windows XPのLet's note CF-Y4JWで行っています。CPU 1.6GHz／RAM 1GBと、個人的には少し頑張って投資してみた環境です。世間的にはいたって普通の環境だと思います。
概要
C++のSTLで書くことができるソート処理は、大まかに次のようなものが考えられます。
| ソート処理 | 説明 |
std::sort() | <algorithm>に入っているソートアルゴリズム。 |
std::multiset<> | <set>に入っているコンテナ。データを追加するとソートされた形で格納されていく。 |
std::list<>::sort() | <list>に入っているコンテナ。listコンテナにはsort()メソッドが付いている。 |
qsort() | C言語で提供されているライブラリ。C++ではまず使わない（速度比較用）。 |
これらのコードの処理速度を計測し、可読性と処理速度の関係から「C++ STLソート処理を書くなら、まずはこれ！」というコードを探します。
計測方法
基本方針としては、Win32APIにあるtimeGetTime()関数を使って1/1000秒単位の処理時間を計測します。
timeGetTime()関数は、システムが起動してからカウントし続けている時間を取得する関数です。この関数を、計測したい処理に挟む形で呼び出し、結果を引き算することで処理にかかった時間が計測できます。
unsigned long start_time = timeGetTime() ; // 計測開始時間 // 計測したい処理をここに挟む。 unsigned long end_time = timeGetTime() ; // 計測終了時間 printf( "%d\t", end_time - start_time ) ; // 表示
timeGetTime()関数に必要なヘッダファイルは次のとおりです。
#include <windows.h> // mmsystem.h の中で UINT とか使っているので必要 #include <mmsystem.h> // timeGetTime() #pragma comment( lib, "winmm.lib" ) // timeGetTime() リンク指定
また、timeBeginPeriod()とtimeEndPeriod()関数を使ってシステムのタイマーの精度を変更します。
timeBeginPeriod()を使わないデフォルトの状態では5～10msの精度になっています（筆者の環境では、おおよそ10msの精度でした）。これをより細かく計測するために、処理の最初と最後に次のようなコードを入れて、1msまで細かく精度を設定します。
timeBeginPeriod( 1 ) ; // タイマーの精度を 1ms にする // すべての処理をここに挟む。 timeEndPeriod( 1 ) ; // タイマーの精度を元に戻す
