クイックソートの高速化を試みた / 認知療法の書籍を読みはじめた

６月８日の日記。

午前９時過ぎに起きた。（だんだん早くなって来た！）

出かけることはなかった。

日中は、クイックソートと挿入ソートをおりまぜたソートアルゴリズムの高速化を試みていた。

先日の記事で述べたマージソートのアルゴリズムで並列化を行なったが、並列化の部分はそのままに、マージソートを行なっている部分をクイックソートで置き換えた。

良いピボットの選択

クイックソートで重要な要素の一つが、ピボットの選び方だ。

クイックソートでは、数列を，チビ（ピボットより小さい値からなる部分列）とデカ（ピボットより大きい値からなる部分列）に分割し、そのチビとデカそれぞれに対してさらに同じような分割を行ない……ということを繰りかえすことでソートを行なう。ピボットは、言うなれば分割の基準となる値だ。

クイックソートでは、分割処理で列がちょうど半分ずつになると、最も効率が良くなる。言い換えると、列をちょうど半分に分割するようなピボットが選ばれることで、最も効率が良くなる。たとえば、 7 個の要素からなる列に対する分割処理では、チビ 3 個，ピボット 1 個，デカ 3 個となるのが望ましい。

逆に最も効率が悪くなるのは、（ピボットを除いて）すべての要素がチビに属するか，すべての要素がデカに属するときだ。たとえば、 7 個の要素からなる列で、チビ 6 個，ピボット 1 個，デカ 0 個となると効率が悪い。

つまりピボットとして部分列の最小の値や最大の値が選ばれると、最も悪い分割が行なわれる。最も良い分割が行なわれるためには、ピボットとして部分列の中央値が選択されなければならない。

さて、列から中央値を選択しようにも、正確に列の中央値を計算するわけには行かない。そのようなことをすれば、その中央値の計算に時間がかかり、（ピボットの選択は何度も行なわれる処理なので）クイックソート全体の実行時間が飛躍的に増大する。そこで、適当に 3 つの要素を選択し、その 3 つの要素の中央値を計算してピボットとするという手法が常套とう手段として存在している。こうすれば、すべての値が異なるという前提においては、少なくとも最悪の分割が行なわれることはない。今回は、実際にこの手法を適用した。

すべての要素が同等の列への対策

実際のところ、列の値はすべて異なるとは限らない。

部分列の分割で、（ピボット以外で）ピボットと同じ値が存在することがある。それでも、その要素をチビとデカのどちらかに所属させなければならないのは言うまでもない。

ここで、そのような要素をチビかデカに無作為に所属させるわけにも行かない。常にチビに所属させるか、常にデカに所属させるかのどちらかになる。今回は常にチビに所属させることにした。よって、チビの定義は「ピボットより小さい値からなる部分列」でなく「ピボット以下の値からなる部分列」となる。

さて、ソート対象の列のすべての要素が同等だとすると、ピボット以外のすべての要素がチビに属することになり、最も悪い分割が繰りかえされることになる。すべてが同じ値からなる列の分割を繰りかえさないためには、すべてが同等であるかを判定する必要がある。

しかし、常にこの判定を行なうわけには行かない。これには要素の数に比例する時間がかかるので、（中央値の例のように）クイックソート全体の実行時間が飛躍的に増大する。実際のところ、列のすべての要素が同等なら、その列が分割されたとき，必ずデカの数が 0 になっている。まずはデカの数が 0 であるかを確認し、その場合のみ特別にすべての要素が同等であるかを判定すればよい。もしすべての要素が同等であれば、その列は自明にソート済みだから、チビに対する分割を行なう必要はない。これで、悪い分割の繰り返しを避けられる。

実行時間計測

このようにして Java で実装したアルゴリズムと、既存のライブラリとの実行時間の比較を行なった。ただし、前回のようにいろいろな高速化の手法を適用するかしないかで複数のパターンを用意することは，もはや行なっていない。

1000万個の32ビット整数のソートをそれぞれ64回行なった。

アルゴリズム	並列化	かかった時間（平均）	かかった時間の標準偏差
Collections.sort	いいえ	3754 ms	461 ms
Stream#sorted	いいえ	3636 ms	19 ms
Stream#sorted	はい	1530 ms	330 ms
クイックソート＆挿入ソート	はい	1170 ms	31 ms

少なくとも十分にランダムなデータでは、既存のライブラリよりも平均的に高速であるようだ。

Stream#sorted （並列化）とクイックソート＆挿入ソートの t 検定を行なったところ、 $t = 8.689$ だった。これで有意に差があると言えるのか私にはわからないが〔たぶんある（笑）。〕。

認知療法の書籍『フィーリング Good ハンドブック』を読みはじめた。「序文」と「はじめに」を読んだ。

「序文」と言うと短そうだけど、けっこう長かった。20ページぐらいあるかも。

序文では、うつ病に対する認知療法の効果が述べられていた。従来、うつ病に対する有効な対策は薬物療法だと考えられて来たが、『フィーリング Good ハンドブック』の前著『いやな気分よ，さようなら』による読書療法を用いた実験で、認知療法には薬物療法と同等かそれ以上の効果があるという研究結果があるという。

また、薬物療法や心理療法では治療後にうつが再発するケースが典型的に存在するのだが、認知療法では再発の割合が薬物療法よりも少ないという。さらに、薬物療法や心理療法では、治療を途中でやめる人が多いのに対し、認知療法ではそのようなことが少なかったという。

「はじめに」では、『フィーリング Good ハンドブック』で認知療法を行なうにあたってやらなければならないことなどが書かれていた。それは