読者です 読者をやめる 読者になる 読者になる

藻のブログ

日記,IT,学問(ジェンダー,人工知能など)について書かれることでしょう。

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

6月8日の日記。


午前9時過ぎに起きた。(だんだん早くなって来た!)

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


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

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

良いピボットの選択

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

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

クイックソートでは、分割処理で列がちょうど半分ずつになると、最も効率が良くなる。言い換えると、列をちょうど半分に分割するようなピボットが選ばれることで、最も効率が良くなる。たとえば、 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 ハンドブック』で認知療法を行なうにあたってやらなければならないことなどが書かれていた。それは

  1. 1週間に1回,本書にある自己評価用テストを完成させること
  2. 人々を怒らせ,悲しませ,失望させ,心配させるような典型的な状況において,あなたがどのように考え,感じ、行動するかを書き留めてもらいたいということ

だ。そして、実際にこれを行なうことで認知療法の効果があるのだと強調されていた。

これは大変そうだ……。

ところで、「はじめに」では次のように書かれていた。

もしも,憂うつになっていれば,「何もかも望みがない。私は敗北者だ。私の気分が良くなることは決してないだろう」と考えているかもしれません。

まさに私だ。すごい!

フィーリングGoodハンドブック

フィーリングGoodハンドブック


水曜日は「掲示板 / メーリングリスト サーバ構築」の日だが、やっぱりなにもやっていない。無力感だけが積み重なって行く。