SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

C++におけるデータのソート方法の比較

STLでの最適なソート方法の検討


  • X ポスト
  • このエントリーをはてなブックマークに追加

本稿では、C++のSTLにいくつか存在する「データのソート方法」について、速さや可読性といったさまざまな観点から検証して、比較します。

  • X ポスト
  • このエントリーをはてなブックマークに追加

はじめに

 この記事の目的は、「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と、個人的には少し頑張って投資してみた環境です。世間的にはいたって普通の環境だと思います。

*1
 筆者個人のブログに詳細を書いてます。
*2
 こんな素晴らしい開発環境がフリーで手に入るなんて、素晴らしいことですね。

概要

 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 ) ;   // タイマーの精度を元に戻す

次のページ
コードの解説

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

山崎 敏(ヤマザキ サトシ)

フリーでプログラミングの仕事をしたり、本や雑誌の原稿を書いたり、株の売買をしたりして、つつましく暮らしております。よろしくお願いします。やまざき@BinaryTechnology

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/394 2006/05/30 11:58

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング