Life Goes On

まあまあだけど楽しんでる方です

今日の教訓

よくあるクイックソートのプログラムを List モジュールの sort 関数(マージソート)と比べてみました。

import Data.Ratio

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (l:ls) =
    quickSort (filter (< l) ls) ++ [l] ++ quickSort (filter (> l) ls)

list :: [Ratio Int]
list = [1%2, 19999%50000, 49999%50000]
*Main> List.sort list
[49999%50000,19999%50000,1%2]
*Main> quickSort list
[19999%50000,1%2,49999%50000]

あれ?結果が違う!sort 関数にバグが!とか思ったら、何のことはない。
19999/50000 と 49999/50000 の比較で桁あふれを起こしていました。
クイックソートの場合は、最初の比較で両者が別のリストに仕分けられるので、たまたま問題がなかったのです。


結論:Ratio Int は使用禁止。


いや Project Euler を解いていて、3,000,000個くらいの Rational のリストをソートしてたらページングを始めたので、少しでもメモリを節約しようと Ratio Int にしてみたのです。
Double にするべきでした。