今日の教訓
よくあるクイックソートのプログラムを 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 にするべきでした。