Haskellでリストのソート（その壱）
qsort (x:xs) = (qsort [y| y <- xs, y < x]) ++ [x] ++ (qsort [z| z <- xs, z >= x])
qsort _ =
これはHaskellで書いたクイックソートなんですが、何ですかこの短さは！
やばいですよね。しかもかなり直感的なソースですよね。
しかし待ってください、これよく見るとちょっと不効率くさくないですか？
まず
[y| y <- xs, y < x]
これです。これ。これは、リストxsの中からx未満の値を全て取り出して繋げるって事だと思うんですが、その後の
[z| z <- xs, z >= x]
は、リストxsの中からx以上の値を全て取り出して繋げるなんですよ！？
ってことは、最初の [y| ...] でx未満の値とx以上の値は全て判明してるのに、
その後にもう一度 [z| ...] でxsの全ての要素を見るのは激しく無意味ですよね。
じゃあ早速それを修正してみることにしましょう。
import List
qsort_plus (x:xs) = qsort_plus rs ++ [x] ++ qsort_plus ls where
(rs, ls) = partition (\ y -> y < x) xs
qsort_plus _ =
ふう。これで何とか。・・・ん？でもまてよ？
Haskellで現在操作しているリストは、あくまでリストの先頭のはず・・・。
ということは、リスト同士を連結するにはリストの終端まで
演算子 `++' は右結合なので、処理順序は (qsort rs ++ ([x] ++ qsort ls)) になるな・・・。
[x] は要素一つだから (x : qsort ls) と同じだから良いとして、qsort rs ++ は
平均で xs の半分の長さを持つリストを末尾まで手繰ることになるのでは・・・。
平均半分だから、ソーティング処理全体でO(n)のコストが掛かりますね。これはマズイ、ということで早速直しましょう。
import List
qsort_plusPlus xs = qsort' xs where
qsort' l = l
qsort' (x:xs) l = qsort' rs (x : (qsort' ls l)) where
(rs, ls) = partition (\ y -> y < x) xs
ふう。これで何とか。・・・ん？でもまてよ？
本当に効率良くなっているのか？ひょっとしたらコンパイラが++を最適化して、末尾の参照を先頭と一緒に保持しているかもしれないし・・・。
（流石にそれはないだろう。）
というわけで、実際にベンチマークをとって見ましょう。以下がそのコードになります。
（ソート処理の定義は省略。）
import Monad
import System
import List
import Hugs.Time
import Random
{- 乱数のリスト -}
rand seed = (randoms $ mkStdGen seed) :: [Int]
{- ソートされてるかチェック -}
isSorted (x:xx:xs)
| x < xx = isSorted (xx:xs)
| otherwise = False
isSorted _ = True
{- 多分ナノ秒を返す -}
now = do (sec, nsec) <- getClockTimePrim
return $ toInteger sec * 1000000 + toInteger nsec
{- 平均を計算(修正) -}
average [] = 0
average xs = div (sum xs) $ toInteger $ length xs
{- 平均を計算 -}
start sorter m n seed =
mapM (speedOf sorter n) (take m $ rand seed) >>= print . average
{- ソートする -}
speedOf sorter n seed = do
before <- now
if not $ isSorted $ sorter $ take n $ rand seed
then error "This sorter is crazy."
else now >>= (\ x -> return (x - before))
main =
do {
print "Hello, I am a pen.";
(seed, _) <- getClockTimePrim;
start (qsort) 100 1000 seed;
start (qsort_plus) 100 1000 seed;
start (qsort_plusPlus) 100 1000 seed;
}
実行結果:
781117
803609
773490
・・・(゜Д゜)(ﾟдﾟ)( Д ) ﾟﾟ
orz
# at 2006/3/24 14:23
平均の計算が間違っていたので修正して再計算。その結果↓リストの長さ1000
759400 - qsort
757080 - qsort_plus
757090 - qsort_plusPlus
