通过递归检查尾部来迭代列表的性能

Question

我决定尝试通过做一些CodinGame挑战来学习Haskell (所以这个问题是超级初学者级的东西,我敢肯定).其中一个需要在整数列表中搜索任意两个值之间的最小差异.我以前通过这样做在Clojure中解决了它:

(ns Solution
  (:gen-class))

(defn smallest-difference [values]
  (let [v (sort values)]
    (loop [[h & t] v curr-min 999999]
      (if (nil? t) curr-min
        (let [dif (- (first t) h)]
          (recur t (if (> curr-min dif) dif curr-min)))))))

(defn -main [& args]
  (let [horse-strengths (repeatedly (read) #(read))]
      (let [answer (smallest-difference horse-strengths)]
        (println answer)))) 

我尝试在Haskell中实现相同的解决方案,具体如下:

readHorses :: Int -> [Int] -> IO [Int]
readHorses n h
    | n < 1 = return h
    | otherwise = do
        l <- getLine
        let hn = read l :: Int
        readHorses (n - 1) (hn:h)

findMinDiff :: [Int] -> Int -> Int
findMinDiff h m
    | (length h) < 2    = m
    | (h!!1 - h!!0) < m = findMinDiff (tail h) (h!!1 - h!!0)
    | otherwise         = findMinDiff (tail h) m



main :: IO ()
main = do
    hSetBuffering stdout NoBuffering -- DO NOT REMOVE
    input_line <- getLine
    let n = read input_line :: Int
    hPrint stderr n
    horses <- readHorses n []
    hPrint stderr "Read all horses"
    print (findMinDiff (sort horses) 999999999)
    return ()

对于Clojure解决方案没有的大输入(99999值),这次超时.然而,它们看起来与我很相似.

至少从表面上看,读取值并构建列表不是问题,因为在超时之前会打印"Read all horses".

如何使Haskell版本更高效？

Answer 1

你计算length每次递归的列表findMinDiff.因为length花费O(n)时间findMinDiff需要O(n^2)时间而不是O(n).

你可以写同样的事情与模式匹配,而不是length,!!和tail

findMinDiff :: [Int] -> Int -> Int
findMinDiff (h0 : hs@(h1 : _)) m = 
    if h1 - h0 < m
    then findMinDiff hs (h1 - h0)
    else findMinDiff hs m
findMinDiff _ m = m