SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。|STLで非常によく使用するsortというアルゴリズムがあるが、規格上は実装方法が規定されていないらしい。n)なんだろうと勝手に思っていたが、よく考えるとクイックソートの最悪計算量はO(n^2)である。これを突いてチャレンジ・・なんて聞いたことがないので多分大丈夫なんだろうと思ったが心配になったので調べてみた。計算量が規定されていれば早いのだが規定を調査しきれなかったのでソースを調べてみた。ついでにVC++2010も同様。FAQによると、gccについては以下のような環境とのこと。4.0.2のソースをWebでダウンロード*1すると、libstdc++-3が付いてきたので、この中にあるstl_algo.hというファイルを見てみる。(おそらくこいつがalgorithm関連のソースだろう)stl_algo.h内のsort関数の実装は以下のようになっていた。}見るからにイントロソートしたあと挿入ソートする、と読める。イントロソートというのは、最初はクイックソートするのだが再帰回数がリミットを超えるとヒープソートに切り替えるというものである。n)だが、実行上はループ内部の処理の多さからクイックソートに平均計算量で劣る。最悪計算量はクイックソートより良いので、良いとこ取りをしようということである。ここではヒープソートに切り替えるリミット(再帰の深さ)を3つ目の引数でlog2(n)*2に指定している。イントロソートしているのにその後挿入ソートをしているのは高速化のためである。実はイントロソートの関数内では要素数がある閾値以下になると処理を終了するようになっている。その結果イントロソート終了後は、ほとんどソートされた配列ができることになる。ほとんどソートされた配列に対しては、挿入ソートが非常に高速に(クイックソートよりも速く!)働くのでこのような実装となっている(と想定される)。イントロソートは以下のような実装になっている。}__depth_limitが0になるとpartial_sortを実行している。partial_sortをするのかというと単にここではpartial_sortをヒープソートで実装しているからである。(partial_sortはヒープソートで実装すると効率がいい)また、要素数が_S_threshold以下になるとイントロソートを終了する。_S_thresholdはstl_algo.h内で以下のように定義されている。};上記以外の場合、クイックソートを実行する。これは__unguarded_partitionで実現されている。(クイックソートのpartition操作にあたる)partial_sortは以下のようになっている。}見ての通りヒープソートのようである。いうことでSTLのsortは最悪時でも高速そうだということが分かったので安心した。ついでに普段ローカルで使用しているVC++2010についても調べてみた。(インストールするとSTLのソースが付いてきます)書き方やパラメータは多少異なるが考え方は同じで、イントロソート+挿入ソートで書かれていた。以上から類推するに、sortの実装はイントロソート+挿入ソートが一般的に効率的な手法なんでしょうね。Hatのglibcは色々バグ修正などがバックポートされていたりするので正確にはコミュニティ版とは異なるところもありますが、アルゴリズムに大きな違いはないだろうと思うので今回はコミュニティ版で確認しています。正確を期すなら、RedHatからSRPMをダウンロードする必要があります。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター357877リンク集SigmarのProfile。