次の項目のタイムライン: クイックソートの2種類の実装法で実行速度に顕著な違いが出る
現在のライセンス: CC BY-SA 4.0
9 件のイベント
日時 書式を切り替える | 内容 | ユーザー | ライセンス | コメント | |
---|---|---|---|---|---|
2019年2月1日 13:27 | 履歴 | 編集日時 | OOPer | CC BY-SA 4.0 |
考察を追記
|
2019年1月27日 15:29 | コメント | 追加済み | OOPer |
Ubuntu 16.04を入れたマシンが2GBだったので試してみました。quick1: 18.547525 sec /quick2: 17.622566 sec (Ubuntu 16.04/Celeron [email protected],-O2)、やはりそれほど顕著な差は出ないですね。Core i7マシンとほぼクロック数比例の違いしか出なかった感じです。
|
|
2019年1月27日 3:01 | コメント | 追加済み | OOPer | @komatsuna さん、ご報告ありがとうございます。「アルゴリズム」としては、上下とも平均O(n*log n)の計算量となるQuickSortに合致しているので、何かご自身の環境に特有の事情などを見つけられたら、ご質問に追記するなどしてみて下さい。1億件を実メモリに保持できるかどうかは微妙なようですが、「上」「下」両アルゴリズムともメモリ使用量に大きな差が出ることはないはずなので、なぜそこまで極端な差がつくのかは興味深いところです。乱数が「上」に不利なデータばかりを出力するとは思えないですし、vectorの実装が多少異なっても、そんな大きな差にはならないですから…。 | |
2019年1月27日 2:31 | コメント | 追加済み | komatsuna | レビューありがとうございます。やはり当方の環境なのでしょうか。メモリは全2GBで余力は0.8GB程度です。 | |
2019年1月27日 1:39 | コメント | 追加済み | OOPer |
@komatsuna さん、コードのご提示ありがとうございます。ただ、大して長いコードでもないので、本文中に直接記入していただいた方が良いように思います。将来リンク切れの心配もなくなりますし。ご提示のコード、範囲外アクセスになる可能性があったので、一箇所だけ書き換えさせていただきました。while (pivot < arr[j]) j--; → while (i < j && pivot < arr[j]) j--; 元のままだとj がlow より小さい値になってしまい、時には0より小さくなる可能性もあります。(そう言う意味では「下」アルゴリズムは若干不完全。)こちらの環境はclang(Fastest, Smallest)ですが、1億件に変更して実行結果は、quick1: 7.642276 sec /quick2: 7.591940 sec 。時にはquick2の方が時間がかかる時もあり、私のSwiftコードよりもっと差が少ないと言う結果になりました。「300経っても終わらず」の時からコードを全く修正していないのであれば、そちらの実行環境に何らかの原因がありそうです。メモリが極端に少ない(32bitint が1億件だと約400MB必要)とかはありますでしょうか?
|
|
2019年1月27日 0:32 | コメント | 追加済み | komatsuna | ideone.com/Ehhq0f に書きました。 | |
2019年1月26日 14:25 | コメント | 追加済み | OOPer | @komatsuna さん、大丈夫ではないような差がついていますね。g++での「上」アルゴリズムのコーディングに間違いがある可能性もありそうです。(私は最初「上」アルゴリズムのコードを間違えてしまい、随分悩んでしまいました。)Core i7 3.2GHz Swift 4.2最適化あり1億件ランダムInt(64bit)で、上が9.8秒、下が8.7秒くらいです。g++のコードを示していただければ、修正すべき点を見つけられるかもしれません。 | |
2019年1月26日 14:16 | コメント | 追加済み | komatsuna | 当方での試行結果を追記しました。化石CPUでアレですが「ここまで差がつくだろうか?」というのを疑問に思い今回質問した次第です。「私の環境でswapのコストが高いことに起因している。実装自体は両者とも正しい。」と捉えておいて大丈夫ですかね? | |
2019年1月26日 4:52 | 履歴 | 回答済み | OOPer | CC BY-SA 4.0 |