Top 上へ 目次
ソートに関する解説
前々回のネタに絡んで問合せがあったので、簡単に解説します。
1.クイックソートよりもマージソートの方が速くなる理由
クイックソートとマージソートのアルゴリズムの違いによるものです。
簡単に言ってしまうと、クイックソートは非安定ソート、マージソートは安定ソートであり、要するにクイックソートは一覧を取得した結果によって遅くなる組み合わせが出ます。
ちょっと語弊はありますが、簡単な事例をあげると昇/降順を切り替えるとクイックソートの最悪ケースが作れます。
もっとも、昇/降順の切り替え専用のメソッドを当然用意することになるんですが、ディスクに書かれた状態がよろしくないパターンだと救済のしようがありません。
またファイルシステムの仕組み依存になりますが、ディスクから読み込んでファイル名を列挙した結果、クイックソートの苦手なタイプになることも多々あります。
読みこみが速いフォルダと、遅いフォルダができちゃうわけで、これは面白くありません。
というわけで、現在はマージソートを採用しているわけです。
まぁ、As/Rは1ディレクトリあたり200万ファイルくらいが実用範囲なんでマージソートなわけですが、1千万ファイル辺りまでサポートするようにするなら、アイテム数によってクイックソートに切り替えた方が良いかもしれません。
余談ですが、並び順がほぼ完成している「更新」の時のソートは、挿入ソートを使ってます。
要はTPOにあわせて、色んなアルゴリズムを組み合わせてるってことです。
2.CPU依存の設定、アルゴリズム切り替え閾値について
クイックソートにしても、マージソートにしても、いわゆる分割系のアルゴリズムは並び替え対象の数が少ない場合に著しく性能が劣化します。
というわけで数が少ない場合の最速アルゴリズムである、挿入ソートに切り替えるのが一般的な改善手法です。
ただ最近のCPUだとコア数が可変型だったり、省電力機能で積極的に居眠りするので、固定的な切り替えポイントって環境依存になっちゃうんですよね。
というわけで、オプション画面でアルゴリズムの自動チューニング機能を載せてます。
やってる内容は、本体とまるっきり同じソート処理をやってます。
あと目安箱ネタですけど、この値を変えたらモッサリ感が無くなったとかの報告ありましたが、これってCPUの性質を理解してない典型的な例だと思われます。
ちょいと、計測に使ったソフトの表示が小さいので申し訳ありませんが
これ、電源プランを「バランス」と「省電力」に切り替えた場合の、「CPUクロック」のグラフです。
前者だと自動計算させた閾値は18〜30位、後者だと40〜60位をウロウロします。
要するに、CPUの挙動が全然違うので自動チューニングもやり直さないとダメよ・・・ということです。
これは未使用コアをスリープさせるIvyBridge世代のCPUの挙動ですが、電源を完全に切っちゃうHaswell以降の世代だともっと顕著になると思います。