尾を再帰的に調べることによるパフォーマンス

Question

私はCodinGameの課題のいくつかを行うことでHaskellを学ぼうと決めました（この質問は初心者レベルのものです）。それらのうちの1つは、任意の2つの値の間の最小の差について整数のリストを検索することを必要とする。

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() 

大きな入力のためのこのタイムアウト（99999値：

(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では同じソリューションを実装しようとした：私は、以前にこれを行うことにより、Clojureの中でそれを解決してきました）どこClojureソリューションはしません。しかし彼らは私にかなり似ています。

少なくとも、「Read all horses」はタイムアウト前に出力されるため、値を読み込んでリストを構築するのは面倒なことです。

ハスケルバージョンをよりパフォーマンスの高いものにするにはどうすればよいですか？

Answer 1

リストのlengthをすべての再帰でfindMinDiffと計算しています。 lengthはO(n)時間を要しますので、O(n)の代わりにO(n^2)時間を要します。あなたがところでpattern matching代わりの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 

Answer 2

と同じことを書くことができ

次のように、完全に代替実装を書くことができます。 （擬似コードは以下の）

は一つの要素

drop 1 h = [h1, h2, h3 ... 

計算の点別の違い

zipWith (-) (drop 1 h) h = [h1-h0, h2-h1, h3-h2, ... 

を削除リストに

h = [h0, h1, h2 ... 

を取るそして、最小を取ります。フルコード：

minDiff :: [Int] -> Int 
minDiff h = minimum (zipWith (-) (drop 1 h) h) 

これは空のリストでクラッシュすることに注意してください。一方で、ハックは不要です（9999999）。怠け者のおかげで、それは一定の空間でも動作します。

minDiff :: [Int] -> Int 
minDiff [] = error "minDiff: empty list" 
minDiff h = minimum (zipWith (-) (drop 1 h) h) 

あるいは、複数pedantically（しかし全体を尊重）：