Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

インテルTBBによる選択ソートの高速化

スレッドを意識しないマルチスレッドアプリケーション

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2010/04/02 14:00

 この記事では、選択ソートアルゴリズムを「STL」で実装し、インテルが公開しているマルチコアCPU向けのC++テンプレートライブラリ「インテル スレッディング・ビルディング・ブロック」を使ってマルチスレッドによる高速化を試みます。

目次

はじめに

 ソートアルゴリズムの実装は代入/比較/繰り返しなど、プログラミングを学ぶ上での基本がきっちり詰まっていて、ビギナーのトレーニングには格好の題材です。簡単なソートアルゴリズムの代表格といえばバブルソート選択ソートでしょうか。

 この記事では、選択ソートアルゴリズムを「STL」(C++の標準テンプレートライブラリ;Standard Template Library)で実装し、インテルが公開しているマルチコアCPU向けのC++テンプレートライブラリ「インテル スレッディング・ビルディング・ブロック」(インテルTBB)を使ってマルチスレッドによる高速化を試みます。

選択ソートのSTLによる実装

 選択ソート(selection sort)のアルゴリズムはバブルソート以上に単純です。配列 data[N] を昇順にソートするには

data[i]~data[N-1]の中から最も小さい要素を探し、
それとdata[i]とを交換する

を i = 0~N-1 に対してくり返すだけ。data[0]~data[N-1]中の最小要素とdata[0]とを交換すれば、当然data[0]が最小となります。次に(data[0]を除いた)data[1]~data[N-1]中の最小要素をdata[1]と交換するのでdata[1]は2番目に小さい要素となります。以下この操作を繰り返せばソート完了という次第。

 STLの<algorithm>には最も小さい要素(を指すイテレータ)を返すmin_element、および2つの要素をイテレータを介して交換するiter_swapがありますから、選択ソートの実装はきわめて簡単です。

// 選択ソート
template<typename Iterator>
void selection_sort(Iterator first, Iterator last) {
  while ( first != last ) {
    // [first,last)中の最小要素をfirstと交換
    std::iter_swap(first, std::min_element(first,last));
    ++first;
  }
}

 10行足らずで書けてしまう選択ソート、性能はいかがなものでしょう。お試しに文字列の並び、vector<string> をソートしましょうか。前準備としてソートアルゴリズムを関数オブジェクトに仕立てておきます。

class sort_base {
public:
    typedef std::vector<std::string>::iterator iterator;
protected:
  iterator first_;
  iterator last_;
  virtual void do_sort() const =0; // ←導出クラスではコレを再定義して処理を書く
public:
  sort_base(iterator first, iterator last) : first_(first), last_(last) {}
  void operator()() const { 
    do_sort(); // ソートして...
    // 昇順に並んでいることを確認
    assert( std::adjacent_find(first_, last_, std::greater<std::string>()) == last_ );
  }
};

/*
 * 至極真っ当な選択ソート
 */
class normal_sort : public sort_base {
public:
  normal_sort(iterator first, iterator last) : sort_base(first,last) {}
protected:
  virtual void do_sort() const {
    selection_sort(first_, last_);
  }
};

// 関数オブジェクトを評価(実行)し、処理時間を測定する
void execute(const sort_base& sort_fn) {
  tbb::tick_count start = tbb::tick_count::now();
  sort_fn();
  std::cout << (tbb::tick_count::now() - start).seconds() << " [sec]\n";
}

int main() {

  std::vector<std::string> source;
  std::vector<std::string> input;

  { // ソート対象を生成。
    // A..Hの順列(8!個)を用意し、
    std::string value = "ABCDEFGH";
    do { source.push_back(value);
    } while ( std::next_permutation(value.begin(), value.end()) );
    // その順序をかき混ぜる。
    std::random_shuffle(source.begin(),source.end());
  }

  { // フツーに選択ソート
    input = source;
    std::cout << "normal_sort ....... " << std::flush;
    execute(normal_sort(input.begin(), input.end()));
  }
}

  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~) だったり わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準講座 (監修) -...

All contents copyright © 2006-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5