クイック ソート アルゴリズム。 クイックソート

本当に実用的なたったひとつのソートアルゴリズム

クイック ソート アルゴリズム

コンテンツメディア事業本部の新卒エンジニアがお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか? 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで(?)、そのような現実的な場面で、 本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 シンプル・イズ・ベスト!正直言ってベンチマークの噛ませ犬! 2• 「クイック」の名前はダテじゃない!王者の貫禄を見せてやれ! 3• 安定感のある隠れた実力者!魅せるソートで人気も優勝もかっさらえ! 4• 彼氏にしたいソートアルゴリズムNo. 1!数値のソートは任せろ! 5• メモリ大食らいの暴君!現実世界でその夢のようなスピードは出せるのか!? 堂々たるメンツが揃い踏みです。 それぞれのアルゴリズムの説明はここでは省略します。 また、「ヒープソートは?」「スリープソートは?」「ボゴソートは?」などの意見は一切受け付けませんのでご了承ください。 ルール• ランダムにシャッフルされた数字の書かれた 64枚のカード (今回使用したのはのカード)を、• テーブル上で手作業で並び替えて• 要したタイムを競う これを上記5つのソートアルゴリズムでカウンターバランスをとりながら、それぞれ3回ずつ計測しました。 下記のランキングでは3回の計測のうち最短のものを採用しています。 また、暗黙の了解として「カードが4,5枚の場合は目視でソート可(アルゴリズムを意識しなくてよい)」というルールも加えました。 実用的には4,5枚だったらアルゴリズム意識するよりパパッとやったほうが速いでしょうし。 なお、シャッフルについてもそれなりにランダムになるよう、• 麻雀式のごちゃ混ぜシャッフルを1回• ヒンズーシャッフル(一般的なカードシャッフル)を1分間 というルールで行いました。 そして、 ソート後に正しくソートされたかチェックして、間違っていたらやり直しというルールを設けました(マゾい)。 しかもこの記録、少々やり方を工夫した結果です。 最初は単純に2つの束を1つの束にマージし続けていましたが、非常に遅かったので4つの束を1つの束にマージする方法にしたところだいぶ改善されました。 それでも最下位ですが^^; まあソートしている間は 結構楽しいので、ソートに楽しさを求める方は一度お試しあーれ。 4位 クイックソート 記録 3分30秒! クイック(笑) 見た目だけは非常にクイックですね。 上記のGIF動画ではものすごい勢いでカードを捌いているように見えますが、やっぱり無駄な動きが多いのでしょうか。 優勝候補の一角だっただけに残念な結果です。 こちらも少々工夫をしていまして、ピボットを10の倍数にするなどして人間が(私が)一瞬で判断できる値を採用しています。 一枚一枚サクサクとふるい分けていくので体感のスピードはなかなかですが、クイック感を意識しすぎるとミスが出ます。 2回ミスっていたせいで合計5回計測する羽目に……。 はっきりいって人間向きではありません。 3位 挿入ソート 記録 3分02秒! まさかの健闘です。 特徴はなにより 全くスペースを必要としないことですね。 さらに、極めて単純なので脳のリソースもほとんど使いません。 友人と喋りながらでもできそうです。 ただ、圧倒的に地味です。 ソート中のワクワク感を大切にする方にはオススメできません。 あとこちらも1回ミスをしましたが、やり直しの落胆っぷりはクイックソートのそれを遥かに凌駕します。 2位 基数ソート 記録 2分35秒! 基数ソートさんステキ! 安定感もさることながら 安心感が強いです。 特に今回はソート対象が2桁の整数だったため、その力を遺憾なく発揮できたといえるでしょう。 カードの枚数が増えても何とかなりそうな包容力も魅力的ですね。 筆者の個人的な好みを抜きにしてもオススメです。 1位 鳩ノ巣ソート 記録 2分08秒! ということで栄えある一位は鳩ノ巣ソートさんでした! もう完全に力技ですね。 机のスペースをあますところなく使っています。 カードの枚数が増えたらスペースが足りなくなるって? そしたらもっと大きい机を用意すればいいじゃない。 鳩ノ巣ソートさんにはこれからもぜひ、他人に流されずに自分の人生を歩んでもらいたいと思います。 考察 なぜこのような結果になったのでしょうか。 実際にソートしてみて分かったこととしては 「カードを拾い上げる動作が遅い」ということです。 マージソートもクイックソートも、一度机に置いたカードを拾って持ち直す回数が多いのです。 一方で鳩ノ巣ソートは一度置いたカードはずっとそのままで、拾い上げの動作は最後にカードをまとめることろくらいです。 また、 「1対1で比較するより一気に複数を比較するほうが速い」ということです。 人間はマシンと違って「35は17より大きいか」と「35は17, 26, 45, 64, 83に対してどこに位置するか」とでは、判断してカードを並べるのにかかる時間は対して変わらないのではないかと思います。 この記事がみなさまの充実したソートライフの糧になりましたら幸いです。 え?タイトルで「たったひとつの」って言ってるだろって? はて、なんのことやら…… sakmt.

次の

クイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

クイック ソート アルゴリズム

考え方 ばらばらなデータが格納された配列 a[ ] が与えられた場合に、それらをクイックソートで並べ替える手順を、下の図に示します。 まず始めに、「軸要素」と呼ばれるデータ値を決定します。 この値は、データ全体を2つに分割するときのしきい値として使われます。 軸要素は、分割が均等に行われるように選ぶのが望ましいのですが、その選択に時間をかけると、かえって並べ替えの時間を大きくしてしまいます。 一般には、次のような方法がよく用いられているようです。 データの先頭の要素を軸要素とする• ランダムに1つ選ぶ• ランダムに3つ選んで、その中央値を取る• 左から見て最初に得られた2つの異なる値の大きいほうを取る 上の図では、最後の方法で軸要素を決定しています。 データの先頭から軸要素以上のデータを検索し、データの末尾から軸要素未満のデータを検索し、見つかった場合、それぞれを交換します。 この作業を検索ラインが交差するまで続けて、交差した場所でデータを2つに分割します。 分割されたそれぞれのデータに対して同様の処理を繰り返します。 これを再帰的に繰り返していくと、最終的にすべてのデータが小さい順に並び替わります。 Java で書かれたクイックソートアルゴリズムを以下に示します。 の方法を使用しています。 メソッド pivot は、軸要素となるデータの番号を返します。 もし、すべてのデータが同じ値を持つ場合、それ以上の分割は必要ないので -1 を返します。 メソッド partition は、pivot で得られた軸要素を使用してデータを2つのブロックに分割します。 このメソッドは、分割した点の番号を返します。 そして、メソッド quickSort は、与えられた配列 a[ ] の a[i]〜a[j] の範囲を並べ替えます。 データを分割する毎に、再帰的にこのメソッドを呼び出すことで、データの並べ替えを行っています。 計算時間の評価 クイックソートアルゴリズムでは、データを分割しながら、• 軸要素を見つける(pivot)• 軸要素を中心としてデータを2つに分割する(partition) の2つの処理を繰り返します。 したがって、まず、これら2つの処理に要する時間量を求めます。 pivot a,i,j は、配列 a[ ] の i 番目から j 番目までの要素の中から、軸要素として使用するデータの番号を検索します。 したがって、これらの処理にはどちらもデータ数に比例した時間がかかることがわかります。 データの分割がもっとも効率よく行われると、各データは2分割ずつされていきますから、クイックソートの分割の深さは、データ数を N をすると log N になります。 このとき、各深さのデータ数はすべて N ですから、この場合のクイックソートの総時間量は O N log N になります。 しかし、分割がアンバランスになる場合もあります。 最悪の場合は、分割が 1:N-1 に行われつづけた場合で、この場合、クイックソートの分割の深さは N となり、それぞれのデータの深さは N , N , N-1 , N-2 , … , 3 , 2 となります。 また、平均的な場合として、すべて異なる一様分布のデータに対しては、O N log N になることが知られています。

次の

うさぎでもわかるソーティング 応用ソート編 クイックソート・マージソート・シェルソート・ヒープソート

クイック ソート アルゴリズム

はじめに この記事は、 16日目の記事です。 2018年7月19日追記 Twitterにて、さんが、以下のようにツイートされていました。 std::threadについては、良い方法が思いつかなかったのでそのままです…。 従って、ソートの高速化を行うには、マルチコアを使った、クイックソートのスレッド並列化が有効でしょう。 昨今のCPUには、少なくとも2個以上のCPUコアが内蔵されており、これを活用しない手はありません。 なお、クイックソートは不安定ソートであることに注意が必要です。 高速な安定ソートが必要な場合は、例えばマージソートをスレッド並列化する必要があるでしょう。 マージソートのスレッド並列化については、という記事にまとめました。 通常のクイックソート クイックソートのスレッド並列化を考える前に、まず通常のクイックソートの実装について触れておきます。 クイックソートの詳細な解説は他に譲りますが(例えば)、例えばクイックソートの(再帰を使わない)実装は、以下のコードのようになります。 再帰を使わないのは、再帰が深くなりすぎて、スタックがオーバーフローすることを避けるためです。 なお、以下のコードは、およびに載っているコードを参考にさせて頂きました。 A template function. stack. top ; stack. コードは以下のようになります(なおこのコードは、に載っているコードを参考にさせて頂きました)。 A template function. A template function. join ; th2. この閾値については議論の余地があると思うのですが、ここでは深入りせず、500に固定しておきます。 また、「現在の再帰の深さが物理コア数以下の時だけ再帰させる」という点には根拠があり、物理コア数(SMTの有無は関係ないようです)が異なる2台のPCで試行錯誤した結果、こうすると最もパフォーマンスが良くなることが分かりました。 クイックソートのOpenMPによるスレッド並列化 次に、OpenMPを使ったスレッド並列化を試してみましょう。 コードは以下のようになりますが、注意すべきは、 task指示句とtaskwait指示句を使っている点です。 これはOpenMP 3. 0で追加されたキーワードであり、従ってOpenMP 2. 0までしかサポートしていない。 なおこのコードは、参考サイト[3]および参考文献[1]に載っているコードを参考にさせて頂きました)。 A template function. A template function. ただし、gcc 5. 4では、TBBのリンクに必要なlibtbbというライブラリが上手くリンクできないようです(gcc 7. 3でも同様です)。 コードは以下のようになります(なおこのコードは、参考サイト[3]に載っているコードを参考にさせて頂きました)。 A template function. A template function. Clangでも利用できませんが、というプロジェクトがあります)。 なお残念ながら、 ため、 ことが発表されています(また、 )。 コードは以下のようになります(なおこのコードは、および参考文献[1]に載っているコードを参考にさせて頂きました)。 A template function. A template function. 3個目から6個目のオーバーロードは、関数と同様であり、引数にコンテナを直接渡すことができます。 Parallelism TSの解説は他に譲りますが(例えば)、例えばstd::sortをスレッド並列化して実行するには、以下のコードのように記述します。 begin , v. 0では、Parallelism TSの利用に、 と という、非標準のヘッダファイルをインクルードする必要があります。 0におけるParallelism TSの実装は、という名称でGitHubにてオープンソースで公開されている(ライセンスはApache License 2. 0)ので、任意のコンパイラでParallelism TSを試すことができます。 並列ソートのパフォーマンス測定 それでは、以上のスレッド並列化されたソート関数のパフォーマンス(ソート時間)を、std::sortおよび並列化なしのクイックソートと比較してみましょう。 パフォーマンスを測定した環境は、• CPU: Intel Core i7-7820X Skylake-X, Hyper Threading ON 物理8コア論理16コア , SpeedStep OFF, Turbo Boost OFF• ここで、配列の要素を500個から1億個まで変化させ、ソートにかかった時間を測定しました。 ただし、測定回数は10回とし、その平均を結果としました。 Windowsの測定環境は、• OS: Microsoft Windows 10 Enterprise 64bit であり、次の二つのコンパイラで測定しました。 14 Visual Studio 2017 version 15. 3 x64ビルド• 0 Update 3 on Visual Studio 2017 x64ビルド また、Linuxの測定環境は• OS: Linux Mint 18. 3 Sylvia x64 であり、次の二つのコンパイラで測定しました。 Clang 6. 1 llvm 6. 0 Update 3 (コンパイル最適化オプション: -O3 -xHOST -ipo) また、Windows及びLinuxの両方において、使用しているTBBとParallel STLのバージョンは以下です。 TBB: Threading Building Blocks 2018 Update 4• 14 Visual Studio 2017 version 15. 3 の場合 まず、OSがWindowsで、コンパイラがMSVC 14. 14 Visual Studio 2017 version 15. 3 の場合について述べたいと思います。 完全にシャッフルされたデータをソートする場合 まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。 ここで言う「完全にシャッフルされたデータが詰められた配列」とは、例えば、 std :: vector vec 1000000 ; std :: iota vec. begin , vec. begin , vec. end , std :: mt19937 rnd ; 上記のコードのvecのような配列のことです。 測定結果を以下の表にまとめました(単位は秒)。 0000105 0. 0000206 0. 0007854 0. 0001106 0. 0000118 0. 0000488 0. 0000103 1000 0. 0000307 0. 0000458 0. 0017938 0. 0000417 0. 0000193 0. 0000615 0. 0000314 5000 0. 0002282 0. 0002706 0. 0056983 0. 0001117 0. 0000755 0. 0001665 0. 0000541 10000 0. 0004913 0. 0005856 0. 0085671 0. 0001706 0. 0001263 0. 0002249 0. 0000892 50000 0. 0029769 0. 0033045 0. 0193815 0. 0009211 0. 0005671 0. 0006856 0. 0003189 100000 0. 0063660 0. 0069406 0. 0251998 0. 0015111 0. 0011198 0. 0013137 0. 0006927 500000 0. 0371493 0. 0390146 0. 0266544 0. 0111206 0. 0058191 0. 0066502 0. 0036882 1000000 0. 0776207 0. 0803658 0. 0450936 0. 0190282 0. 0113178 0. 0135686 0. 0083812 5000000 0. 4346670 0. 4429705 0. 1116999 0. 0772312 0. 0598766 0. 0680693 0. 0412007 10000000 0. 9163644 0. 9171497 0. 2934905 0. 2847365 0. 1186347 0. 1397822 0. 0871509 50000000 5. 0630314 4. 9998463 1. 4515623 1. 4487035 0. 6638043 0. 7369049 0. 4785176 100000000 10. 619285 10. 357525 2. 6112381 2. 6693424 1. 3470694 1. 5490454 0. 9843640 これをグラフにすると、以下の図のようになります(両対数グラフであることに注意してください)。 TBBは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500~1000個の場合は、TBBはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより遅くなっています)。 原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。 また、TBBとstd::threadは、配列の要素数が1000万個以上になると概ね同じような傾向を示します。 std::threadとTBBは、配列の要素数が1000万個以上では、std::sortよりも3倍強~4倍強程度高速で、並列化なしのクイックソートよりも3倍強~4倍弱程度高速であることが分かります。 配列の要素数が5万個以上の場合、std::sortより5倍強~8倍弱程度高速で、並列化なしのクイックソートよりも、6倍弱~8倍弱程度高速です。 MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortや並列化なしのクイックソートより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortよりよりも4倍強~7倍弱程度高速で、並列化なしのクイックソートよりよりも5倍弱~7倍弱程度高速です。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortより高速であり、配列の要素数によらず並列化なしのクイックソートより高速です。 配列の要素数が5万個以上の場合は、通常のstd::sortよりも9倍強~11倍弱程度高速であり、並列化なしのクイックソートと比べても、9. 5倍~10. 5倍前後高速です。 あらかじめソートされたデータをソートする場合 極端な場合として、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。 ここで言う「あらかじめソートされたデータが詰められた配列」とは、例えば、 std :: vector vec 1000000 ; std :: iota vec. begin , vec. end , 1 ; 上記のコードのvecのような配列のことです。 測定結果を以下の表にまとめました(単位は秒)。 0000022 0. 0000044 0. 0006129 0. 0000077 0. 0000123 0. 0000088 0. 0000022 1000 0. 0000048 0. 0000080 0. 0047579 0. 0000227 0. 0000140 0. 0000174 0. 0000089 5000 0. 0000332 0. 0000451 0. 0045788 0. 0000771 0. 0000158 0. 0000453 0. 0000213 10000 0. 0000710 0. 0000921 0. 0046490 0. 0001623 0. 0000157 0. 0000664 0. 0000332 50000 0. 0004049 0. 0004956 0. 0052971 0. 0007838 0. 0000242 0. 0001726 0. 0000888 100000 0. 0008649 0. 0010173 0. 0062134 0. 0014990 0. 0000345 0. 0002921 0. 0001802 500000 0. 0048160 0. 0048431 0. 0111454 0. 0065952 0. 0001063 0. 0011728 0. 0009167 1000000 0. 0102507 0. 0100107 0. 0181422 0. 0130628 0. 0001778 0. 0023222 0. 0017393 5000000 0. 0651592 0. 0611962 0. 0898387 0. 0819424 0. 0007313 0. 0140111 0. 0102733 10000000 0. 1357622 0. 1279987 0. 1796392 0. 1684790 0. 0013920 0. 0282092 0. 0221214 50000000 0. 7438876 0. 7182626 0. 9452092 0. 9320811 0. 0065915 0. 1444874 0. 1310186 100000000 1. 5588848 1. 4604970 1. 9148640 1. 8876132 0. 0130660 0. 2972128 0. 2600567 これをグラフにすると、以下の図のようになります。 std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が500万個以上では、TBBとよく似た傾向を示すようになります。 配列の要素数が5万個以上の場合、MSVC内蔵のParallelism TSのstd::sortは、通常のstd::sortと比べて2倍強~5倍強程度高速であり、並列化なしのクイックソートと比べて3倍弱~5倍弱程度高速です。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて通常のstd::sortと同じかより高速であり、配列の要素数が1000個の場合を除いて並列化なしのクイックソートより高速です。 配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortよりも4. 5倍強~6倍弱程度高速であり、並列化なしのクイックソートよりも5. 5~6倍前後高速です。 begin , vec. end , std :: mt19937 rnd ; 上記のコードのvecのような配列のことです。 測定結果を以下の表にまとめました(単位は秒)。 0000077 0. 0000155 0. 0006790 0. 0000258 0. 0000239 0. 0000190 0. 0000067 1000 0. 0000217 0. 0000353 0. 0046376 0. 0000684 0. 0000296 0. 0000369 0. 0000296 5000 0. 0001720 0. 0002136 0. 0047161 0. 0002475 0. 0000796 0. 0000890 0. 0000544 10000 0. 0003776 0. 0004529 0. 0051054 0. 0005376 0. 0001177 0. 0001537 0. 0000992 50000 0. 0022752 0. 0025642 0. 0075665 0. 0028267 0. 0004799 0. 0005591 0. 0002598 100000 0. 0048283 0. 0052955 0. 0103339 0. 0059098 0. 0008953 0. 0010035 0. 0005199 500000 0. 0280530 0. 0304428 0. 0363402 0. 0321648 0. 0044743 0. 0051084 0. 0030352 1000000 0. 0591813 0. 0613432 0. 0701248 0. 0645308 0. 0087039 0. 0101671 0. 0059988 5000000 0. 3400867 0. 3401270 0. 3667609 0. 3607571 0. 0464018 0. 0558637 0. 0326124 10000000 0. 7158605 0. 7192092 0. 7553036 0. 7495500 0. 0963697 0. 1061310 0. 0684678 50000000 3. 9531315 3. 8887368 4. 1261271 4. 0954510 0. 4935916 0. 5956207 0. 3806331 100000000 8. 1931949 7. 9252468 8. 3920237 8. 3893786 1. 0313685 1. 1540692 0. 7773747 これをグラフにすると、以下の図のようになります。 std::threadおよびTBBは、配列の要素数によらず、並列化なしのクイックソートよりも遅くなっています(理由はやはり再帰にあると考えています)。 std::threadは相変わらずなぜかパフォーマンスが悪いのですが、配列の要素数が100万個以上では、TBBとよく似た傾向を示すようになります。 配列の要素数が5万個以上の場合、std::sortよりも5倍弱~8倍程度高速であり、並列化なしのクイックソートよりも5倍強~8倍弱程度高速です。 MSVC内蔵のParallelism TSのstd::sortは、配列の要素数が5000個以上で、通常のstd::sortや並列化なしのクイックソートより高速であり、配列の要素数が5万個以上の場合は、通常のstd::sortより約4倍~7倍程度高速であり、並列化なしのクイックソートよりも4. 5倍~7倍弱程度高速です。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が1000個の場合を除いて、通常のstd::sortより高速であり、配列の要素数によらず並列化なしのクイックソートより高速です。 配列の要素数が5万個以上の場合は、通常のstd::sortより9倍弱~10. 5倍程度高速で、並列化なしのクイックソートよりも10倍~10. 5倍程度高速です。 0 Update 3 on Visual Studio 2017 の場合について述べたいと思います。 完全にシャッフルされたデータをソートする場合 まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します(MSVCの場合と同様ですので、コードは省略します)。 測定結果を以下の表にまとめました(単位は秒)。 0000112 0. 0000164 0. 0007436 0. 0006165 0. 0004290 0. 0006597 0. 0000160 0. 0000128 1000 0. 0000385 0. 0000420 0. 0019905 0. 0000526 0. 0000364 0. 0000517 0. 0000219 0. 0000311 5000 0. 0002925 0. 0002809 0. 0067707 0. 0001042 0. 0001108 0. 0002143 0. 0000860 0. 0000744 10000 0. 0006159 0. 0006126 0. 0105863 0. 0001783 0. 0001770 0. 0002441 0. 0001477 0. 0001108 50000 0. 0037654 0. 0035009 0. 0212561 0. 0009066 0. 0009384 0. 0010285 0. 0006311 0. 0003845 100000 0. 0081020 0. 0072381 0. 0272721 0. 0018079 0. 0015905 0. 0016453 0. 0012977 0. 0009076 500000 0. 0411484 0. 0365986 0. 0268489 0. 0117485 0. 0111043 0. 0114088 0. 0058300 0. 0038435 1000000 0. 0840850 0. 0766921 0. 0441507 0. 0203404 0. 0199599 0. 0207461 0. 0115498 0. 0078943 5000000 0. 4760080 0. 4235053 0. 1097566 0. 0818633 0. 0769053 0. 0767336 0. 0631194 0. 0435588 10000000 0. 9974043 0. 8825915 0. 2854968 0. 3022849 0. 2732951 0. 2796027 0. 1210720 0. 0893373 50000000 5. 5457645 4. 8240598 1. 4252771 1. 5601663 1. 4344915 1. 4282759 0. 6983091 0. 4781524 100000000 11. 542163 9. 9299251 2. 5361999 2. 8605935 2. 6061240 2. 5401996 1. 4267306 0. 9885334 これをグラフにすると、以下の図のようになります。 TBBは配列の要素数が1000個以上で、またOpenMP、Cilkは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500個、あるいは1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートより同じか遅くなっています)。 原因は分かりませんが、std::threadはパフォーマンスが悪く、配列の要素数が50万個以上でやっと、std::sortや並列化なしのクイックソートよりも高速になります。 また、OpenMP、TBBは、配列の要素数が5000個以上で概ね同じような傾向を示し、配列の要素数が10万個以上では、これにCilkが加わります。 加えて、配列の要素数が1000万個以上では、さらにこれにstd::threadが加わります。 std::thread、OpenMP、TBB、Cilkは、配列の要素数が1000万個以上では、std::sortより3. 5倍弱~4. 5倍弱程度高速で、並列化なしのクイックソートよりも3倍弱~4倍弱程度高速であることが分かります。 配列の要素数が50万個以上の場合、std::sortと比べて、7倍~8倍程度高速であり、並列化なしのクイックソートよりも6倍強~7倍強程度高速です。 Parallelism TSのstd::sortは、配列の要素数が500個の場合を除いてstd::sortより高速で、配列の要素数に関わらず、並列化なしのクイックソートより高速です。 配列の要素数が5万個以上の場合は、通常のstd::sortと比べて、9倍弱~12倍弱程度高速であり、並列化なしのクイックソートより8倍弱~10倍程度高速です。 あらかじめソートされたデータをソートする場合 次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します(MSVCの場合と同様ですので、コードは省略します)。 測定結果を以下の表にまとめました(単位は秒)。 0000027 0. 0000029 0. 0006413 0. 0000263 0. 0000056 0. 0000080 0. 0000127 0. 0000044 1000 0. 0000095 0. 0000066 0. 0059114 0. 0000371 0. 0000188 0. 0000159 0. 0000139 0. 0000096 5000 0. 0000680 0. 0000353 0. 0051308 0. 0000898 0. 0000732 0. 0000705 0. 0000167 0. 0000290 10000 0. 0001460 0. 0000745 0. 0051399 0. 0001532 0. 0001367 0. 0001354 0. 0000207 0. 0000409 50000 0. 0008523 0. 0004131 0. 0059481 0. 0007127 0. 0006883 0. 0006611 0. 0000360 0. 0001048 100000 0. 0018375 0. 0008384 0. 0065833 0. 0014420 0. 0014218 0. 0013477 0. 0000470 0. 0001925 500000 0. 0103541 0. 0034851 0. 0094455 0. 0069455 0. 0068525 0. 0069824 0. 0001189 0. 0010449 1000000 0. 0130985 0. 0069574 0. 0151293 0. 0143057 0. 0139627 0. 0123884 0. 0001910 0. 0017862 5000000 0. 0796871 0. 0436289 0. 0709000 0. 0834809 0. 0678125 0. 0654350 0. 0008728 0. 0106855 10000000 0. 1674286 0. 0913427 0. 1412512 0. 1737078 0. 1372828 0. 1371062 0. 0015763 0. 0243696 50000000 0. 9144676 0. 5113665 0. 7255208 0. 9484902 0. 7217126 0. 7356642 0. 0074194 0. 1261906 100000000 1. 9076368 1. 0650431 1. 4900302 1. 9383843 1. 4831862 1. 5115661 0. 0144612 0. 2537880 これをグラフにすると、以下の図のようになります。 std::sortと比較すると、std::threadは相変わらずなぜかパフォーマンスが悪く、std::sortより高速となっているのは配列の要素数が500万個以上の場合のみです(ただ、配列の要素数が1億個の場合、std::threadはstd::sortより30%弱ほど高速になっています)。 OpenMP、TBBおよびCilkについては、配列の要素数が1万個以上でよく似た傾向を示し、配列の要素数が5万個以上では、std::sortよりも最大で50%程度高速になっています。 ただ、OpenMPは配列の要素数500万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。 配列の要素数が5万個以上の場合、Parallel STLのParallelism TSのstd::sortは、通常のstd::sortと比べて、7倍強~10倍弱程度高速であり、並列化なしのクイックソートより3倍強~4倍強前後高速です。 5倍程度高速です。 測定結果を以下の表にまとめました(単位は秒)。 0000083 0. 0000117 0. 0006612 0. 0000281 0. 0000144 0. 0000164 0. 0000267 1000 0. 0000277 0. 0000282 0. 0053156 0. 0000687 0. 0000367 0. 0000438 0. 0000339 5000 0. 0002233 0. 0002179 0. 0056870 0. 0002779 0. 0002645 0. 0002533 0. 0000920 10000 0. 0004964 0. 0004635 0. 0055099 0. 0005340 0. 0005445 0. 0005217 0. 0001267 50000 0. 0029371 0. 0026732 0. 0079784 0. 0029162 0. 0028928 0. 0028872 0. 0005083 100000 0. 0062987 0. 0053871 0. 0101536 0. 0060433 0. 0061069 0. 0059785 0. 0009695 500000 0. 0313180 0. 0281566 0. 0346996 0. 0344818 0. 0323094 0. 0300344 0. 0046931 1000000 0. 0650140 0. 0578785 0. 0667329 0. 0709481 0. 0646521 0. 0620647 0. 0088882 5000000 0. 3753888 0. 3213315 0. 3491990 0. 3885325 0. 3461711 0. 3494958 0. 0501326 10000000 0. 7755058 0. 6740220 0. 7193811 0. 8073721 0. 7197736 0. 7201322 0. 0975946 50000000 4. 3590371 3. 7176883 3. 9487141 4. 4289383 3. 9589728 4. 0048623 0. 5239695 100000000 9. 0020265 7. 5980535 8. 0375931 9. 0428873 8. 0102797 8. 1078513 1. 0722374 これをグラフにすると、以下の図のようになります。 std::thread、OpenMP、TBB、Cilkは、配列の要素数によらず、並列化なしのクイックソートよりも遅くなっています。 OpenMP、TBBおよびCilkについては、配列の要素数が1万個以上でよく似た傾向を示し、配列の要素数が5万個以上では、std::sortよりも最大で約12%高速になっています。 ただ、OpenMPは配列の要素数100万個以上のパフォーマンスがぱっとせず、std::threadに逆転されています。 配列の要素数が50万個以上の場合、std::sortと比べて、7. 5倍~8. 5倍弱程度高速であり、並列化なしのクイックソートよりも6. 5倍~7倍強程度高速です。 Parallelism TSのstd::sortは、配列の要素数が5000個未満の場合を除いてstd::sortより高速で、配列の要素数が1000個の場合を除いて並列化なしのクイックソートより高速です。 配列の要素数が5万個以上の場合は、通常のstd::sortと比べて、9倍強~11. 5倍程度高速であり、並列化なしのクイックソートより8倍強~10倍弱程度高速です。 Linux - Clang 6. 1 llvm 6. 0 の場合 次に、OSがLinuxで、コンパイラがClang 6. 1 llvm 6. 0 の場合について述べたいと思います。 完全にシャッフルされたデータをソートする場合 まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。 測定結果を以下の表にまとめました(単位は秒)。 0000082 0. 0000176 0. 0000452 0. 0012356 0. 0000697 0. 0000108 0. 0000095 1000 0. 0000270 0. 0000432 0. 0008947 0. 0000403 0. 0000410 0. 0000281 0. 0000284 5000 0. 0002055 0. 0002725 0. 0025421 0. 0000969 0. 0002940 0. 0008250 0. 0020838 10000 0. 0004574 0. 0007737 0. 0035038 0. 0001719 0. 0006230 0. 0067376 0. 0035836 50000 0. 0037939 0. 0033443 0. 0079702 0. 0009191 0. 0070720 0. 0097454 0. 0162332 100000 0. 0057554 0. 0066024 0. 0038643 0. 0016838 0. 0146290 0. 0116198 0. 0024709 500000 0. 0305660 0. 0365841 0. 0122286 0. 0116593 0. 0297616 0. 0063712 0. 0031959 1000000 0. 0636356 0. 0762420 0. 0218816 0. 0201896 0. 0354132 0. 0124700 0. 0066840 5000000 0. 3541420 0. 4180345 0. 0781733 0. 0836665 0. 0955434 0. 0599293 0. 0383507 10000000 0. 7393443 0. 8686349 0. 2739279 0. 2962601 0. 2982571 0. 1217534 0. 0822734 50000000 4. 0685265 4. 7451769 1. 3936217 1. 5330745 1. 4061053 0. 6486228 0. 4484733 100000000 8. 4711877 9. 8086634 2. 5069266 2. 8265746 2. 5259248 1. 3069129 0. 9327233 これをグラフにすると、以下の図のようになります。 Windowsの場合と比べて、ややばらついた結果となっています。 OpenMPは、配列の要素数が5000個以上で、std::sortや並列化なしのクイックソートよりも高速になります(配列の要素数が500~1000個の場合は、これらはスレッド生成のコストが高くつくため、std::sortや並列化なしのクイックソートとほぼ同じか遅くなっています)。 std::threadについては、Windowsの場合と異なり、パフォーマンスはそれほど悪くありません。 実際、std::threadは、配列の要素数が10万個以上で、std::sortや並列化なしのクイックソートよりも高速になります。 TBBは、いくつか例外はあるものの、配列の要素数が50万個でstd::sortや並列化なしのクイックソートより若干高速となり、配列の要素数100万個以上では、std::sortや並列化なしのクイックソートよりも明らかに高速になっています。 また、OpenMPは配列の要素数1億個のパフォーマンスがぱっとせず、std::threadおよびTBBに逆転されています。 また、std::threadとOpenMPは、配列の要素数が50万個以上になると概ね同じような傾向を示し、配列の要素数が500万個以上では、これにTBBが加わります。 std::thread、OpenMP、TBBは、配列の要素数が1000万個以上では、std::sortよりも2. 5~3倍強程度高速で、並列化なしのクイックソートよりも3倍弱~4倍弱程度高速であることが分かります。 5倍程度高速であり、並列化なしのクイックソートより6倍弱~7. 5倍程度高速です。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が10万個以上で、通常のstd::sortおよび並列化なしのクイックソートより高速になります(ただし、配列の要素数が500~1000個の場合、Parallel STLのParallelism TSのstd::sortは並列化なしのクイックソートよりも高速になっています)。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が50万個以上で、通常のstd::sortよりも9倍強~9. 5倍程度高速であり、並列化なしのクイックソートより10. 5倍~11. 5倍程度高速です。 5倍弱~2倍弱程度高速です(配列の要素数が10万個の場合は、前者は後者に比べて4. 7倍ほど高速になっています)。 あらかじめソートされたデータをソートする場合 次に、あらかじめソートされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。 測定結果を以下の表にまとめました(単位は秒)。 0000039 0. 0000036 0. 0000293 0. 0011182 0. 0000190 0. 0000787 0. 0000033 1000 0. 0000071 0. 0000088 0. 0007118 0. 0000374 0. 0000182 0. 0000393 0. 0000073 5000 0. 0000483 0. 0000538 0. 0015674 0. 0001045 0. 0000909 0. 0000445 0. 0000433 10000 0. 0001047 0. 0001119 0. 0004463 0. 0001898 0. 0001850 0. 0000498 0. 0000889 50000 0. 0006514 0. 0006585 0. 0011631 0. 0009409 0. 0023101 0. 0072143 0. 0003620 100000 0. 0014324 0. 0022156 0. 0021136 0. 0019272 0. 0033720 0. 0102214 0. 0074801 500000 0. 0076411 0. 0066656 0. 0072039 0. 0094773 0. 0115869 0. 0115223 0. 0007200 1000000 0. 0084903 0. 0096681 0. 0135786 0. 0191987 0. 0242018 0. 0013136 0. 0011146 5000000 0. 0531632 0. 0577156 0. 0779753 0. 1112065 0. 1015973 0. 0005733 0. 0071112 10000000 0. 1127137 0. 1202401 0. 1626628 0. 2306885 0. 2032101 0. 0010204 0. 0175606 50000000 0. 6398618 0. 6757863 0. 8924792 1. 2693008 0. 9598112 0. 0045571 0. 0970528 100000000 1. 3435503 1. 3915084 1. 8296449 2. 6020277 1. 9420743 0. 0089462 0. 2036036 これをグラフにすると、以下の図のようになります。 これもWindowsの場合と比べると、結果がばらついています。 std::thread、OpenMP、TBB、Cilkは、配列の要素数によらず、std::sortおよび並列化なしのクイックソートよりも遅くなっています。 しかし、配列の要素数500万個以上では、std::sortおよび並列化なしのクイックソートと比べて桁違いに高速となります。 Parallel STLのParallelism TSのstd::sortは、std::sortおよび並列化なしのクイックソートと比べ、配列の要素数が1000個および10万個の場合を除いて高速です。 特に、配列の要素数50万個以上では、std::sortや並列化なしのクイックソートと比べて速度で優位に立ちます。 配列の要素数が50万個以上の場合、Parallel STLのParallelism TSのstd::sortは、std::sortと比べて、6倍強~10倍強程度高速であり、並列化なしのクイックソートと比べて7倍弱~9倍強高速となっています。 測定結果を以下の表にまとめました(単位は秒)。 0000057 0. 0000124 0. 0000499 0. 0000318 0. 0000106 0. 0000150 0. 0000065 1000 0. 0000184 0. 0000321 0. 0019767 0. 0000664 0. 0000379 0. 0000317 0. 0000199 5000 0. 0010089 0. 0002181 0. 0005501 0. 0002711 0. 0002543 0. 0001953 0. 0058662 10000 0. 0003625 0. 0004642 0. 0013484 0. 0011022 0. 0014804 0. 0052794 0. 0004146 50000 0. 0021589 0. 0033035 0. 0031971 0. 0029864 0. 0041919 0. 0097452 0. 0057634 100000 0. 0051278 0. 0054304 0. 0059275 0. 0062049 0. 0072869 0. 0139083 0. 0058345 500000 0. 0231042 0. 0285078 0. 0308658 0. 0351382 0. 0380815 0. 0047281 0. 0024596 1000000 0. 0487949 0. 0583199 0. 0626893 0. 0715997 0. 0792592 0. 0092865 0. 0052220 5000000 0. 2758546 0. 3208566 0. 3421503 0. 3889630 0. 3597205 0. 0483009 0. 0296392 10000000 0. 5679869 0. 6739331 0. 7115292 0. 8050502 0. 7370682 0. 1029519 0. 0642536 50000000 3. 1428122 3. 6859859 3. 9115053 4. 4406249 3. 9799025 0. 5014625 0. 3498908 100000000 6. 6013517 7. 5374835 7. 9889059 8. 9916836 8. 1118474 1. 0711941 0. 7272231 これをグラフにすると、以下の図のようになります。 これもWindowsの場合と比べると、結果がばらついています。 std::thread、OpenMP、TBB、Cilkは、配列の要素数500個や5000個の場合など、一部の例外を除き、std::sortおよび並列化なしのクイックソートよりも遅くなっています。 Parallel STLのParallelism TSのstd::sortは、配列の要素数が50万個以上の場合は、std::sortよりも9倍~9倍強程度高速であり、並列化なしのクイックソートより10. 5倍~11. 5倍程度高速です。 5倍強~2. 5倍弱程度高速です(配列の要素数が5000個~10000個の場合は例外です)。 0 Update 3の場合について述べたいと思います。 完全にシャッフルされたデータをソートする場合 まずは、完全にシャッフルされたデータが詰められた配列の要素をソートする場合のパフォーマンスを測定します。 測定結果を以下の表にまとめました(単位は秒)。 0000079 0. 0000169 0. 0000656 0. 0002873 0. 0001826 0. 0000580 0. 0000122 0. 0000102 1000 0. 0000285 0. 0000433 0. 0022957 0. 0000424 0. 0000421 0. 0000382 0. 0000310 0. 0000315 5000 0. 0002369 0. 0005216 0. 0012250 0. 0000906 0. 0002992 0. 0007747 0. 0050822 0. 0032201 10000 0. 0005206 0. 0007270 0. 0023432 0. 0001627 0. 0018862 0. 0011383 0. 0076266 0. 0057093 50000 0. 0029666 0. 0031581 0. 0024698 0. 0009580 0. 0035261 0. 0079922 0. 0032476 0.

次の