Haskell性能:反转计数算法

Question

我决定使用Haskell 从Standford算法课程https://class.coursera.org/algo-005解决第一个编程任务.尽管我对语言很陌生,但我实现它的速度比c ++快得多.我有6年以上的c ++工作经验,所以给我留下了深刻的印象.但性能令人失望:0.19秒(c ++)vs 9.88(haskell)版本.如何提高Haskell实现的性能,使其可以与c ++相媲美？

这是我在Haskell中的代码

data SortedList = SortedList {
    inversionCount :: Int,
    list :: [Int]
} deriving (Show) 

--      first   list        accumulator
packm :: Int -> SortedList -> Int -> SortedList
packm x (SortedList count xs) add =  SortedList (count + add) (x:xs)

merge2 :: [Int] -> [Int] -> SortedList
merge2 [] xs = SortedList 0 xs
merge2 xs [] = SortedList 0 xs
merge2 xlist@(x:xs) ylist@(y:ys)
    | x < y = packm x (merge2 xs ylist) 0
    | otherwise = packm y (merge2 xlist ys) $ length xlist

countAndMerge :: SortedList -> SortedList -> SortedList
countAndMerge (SortedList lcount lxs) (SortedList rcount rxs) =
    let merged = merge2 lxs rxs
    in SortedList (lcount + rcount + inversionCount merged) $ list merged

mergesort :: [Int] -> SortedList
mergesort [] = SortedList 0 []
mergesort [x] = SortedList 0 [x]
mergesort xs =
    let leftsorted = mergesort $ take halfElements xs
        rightsorted = mergesort $ drop halfElements xs
    in countAndMerge leftsorted rightsorted
    where halfElements = length xs `div` 2

main = do 
    contents <- getContents
    let intlist = [ read x :: Int | x <- (lines contents) ]
    print $ inversionCount $ mergesort intlist

Answer 1

最大的问题是渐近的表现是不正确的; 它是O(n ^ 2*log n)而不是最优O(n*log n).罪魁祸首是merge2:

    | otherwise = packm y (merge2 xlist ys) $ length xlist

length xlist是O(n).假设一个随机输入列表,我们需要计算length xlist大约一半的merge2调用,从而使一个级别的合并O(n ^ 2).