Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-23STLのsortの計算量

STLのsortの計算量

| 22:55 | STLのsortの計算量 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - STLのsortの計算量 - SRM diary(Sigmar) STLのsortの計算量 - SRM diary(Sigmar) のブックマークコメント

STLで非常によく使用するsortというアルゴリズムがあるが、規格上は実装方法が規定されていないらしい。

何となくクイックソートで実装されてて計算量はO(n log n)なんだろうと勝手に思っていたが、よく考えるとクイックソートの最悪計算量はO(n^2)である。

これを突いてチャレンジ・・なんて聞いたことがないので多分大丈夫なんだろうと思ったが心配になったので調べてみた。

計算量が規定されていれば早いのだが規定を調査しきれなかったのでソースを調べてみた。


結論:Topcoder Arenaで使用するSTLのsortは平均計算量O(n log n)、最悪計算量O(n log n)である。

ついでにVC++2010も同様。


TopcoderのWeb FAQによると、gccについては以下のような環境とのこと。

General SRM Algorithm FAQ

Linux 2.6.9-55.0.12.ELsmp, gcc 4.0.2 (RedHat EL 4), glibc-2.3.2, and libstdc++-3.

gcc 4.0.2のソースをWebでダウンロード*1すると、libstdc++-3が付いてきたので、この中にあるstl_algo.hというファイルを見てみる。

(おそらくこいつがalgorithm関連のソースだろう)


stl_algo.h内のsort関数の実装は以下のようになっていた。

  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      if (__first != __last)
	{
	  std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
	  std::__final_insertion_sort(__first, __last);
	}
    }

見るからにイントロソートしたあと挿入ソートする、と読める。

イントロソートというのは、最初はクイックソートするのだが再帰回数がリミットを超えるとヒープソートに切り替えるというものである。

ヒープソートは最悪・平均計算量ともにO(n log n)だが、実行上はループ内部の処理の多さからクイックソートに平均計算量で劣る。

しかし最悪計算量はクイックソートより良いので、良いとこ取りをしようということである。

ここではヒープソートに切り替えるリミット(再帰の深さ)を3つ目の引数でlog2(n)*2に指定している。

なおイントロソートしているのにその後挿入ソートをしているのは高速化のためである。

実はイントロソートの関数内では要素数がある閾値以下になると処理を終了するようになっている。

その結果イントロソート終了後は、ほとんどソートされた配列ができることになる。

ほとんどソートされた配列に対しては、挿入ソートが非常に高速に(クイックソートよりも速く!)働くのでこのような実装となっている(と想定される)。


イントロソートは以下のような実装になっている。

  template<typename _RandomAccessIterator, typename _Size>
    void
    __introsort_loop(_RandomAccessIterator __first,
		     _RandomAccessIterator __last,
		     _Size __depth_limit)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      while (__last - __first > int(_S_threshold))
	{
	  if (__depth_limit == 0)
	    {
	      std::partial_sort(__first, __last, __last);
	      return;
	    }
	  --__depth_limit;
	  _RandomAccessIterator __cut =
	    std::__unguarded_partition(__first, __last,
				       _ValueType(std::__median(*__first,
								*(__first
								  + (__last
								     - __first)
								  / 2),
								*(__last
								  - 1))));
	  std::__introsort_loop(__cut, __last, __depth_limit);
	  __last = __cut;
	}
    }

__depth_limitが0になるとpartial_sortを実行している。なぜpartial_sortをするのかというと単にここではpartial_sortをヒープソートで実装しているからである。

(partial_sortはヒープソートで実装すると効率がいい)

また、要素数が_S_threshold以下になるとイントロソートを終了する。_S_thresholdはstl_algo.h内で以下のように定義されている。

  enum { _S_threshold = 16 };

上記以外の場合、クイックソートを実行する。これは__unguarded_partitionで実現されている。(クイックソートのpartition操作にあたる)


partial_sortは以下のようになっている。

  template<typename _RandomAccessIterator>
    void
    partial_sort(_RandomAccessIterator __first,
		 _RandomAccessIterator __middle,
		 _RandomAccessIterator __last)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;

      // concept requirements
      // アルゴリズムと関係ないので中略

      std::make_heap(__first, __middle);
      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
	if (*__i < *__first)
	  std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
      std::sort_heap(__first, __middle);
    }

見ての通りヒープソートのようである。


ということでSTLのsortは最悪時でも高速そうだということが分かったので安心した。


ついでに普段ローカルで使用しているVC++2010についても調べてみた。

(インストールするとSTLのソースが付いてきます)

書き方やパラメータは多少異なるが考え方は同じで、イントロソート+挿入ソートで書かれていた。

以上から類推するに、sortの実装はイントロソート+挿入ソートが一般的に効率的な手法なんでしょうね。

*1:Red Hatのglibcは色々バグ修正などがバックポートされていたりするので正確にはコミュニティ版とは異なるところもありますが、アルゴリズムに大きな違いはないだろうと思うので今回はコミュニティ版で確認しています。正確を期すなら、RedHatからSRPMをダウンロードする必要があります。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111023