我已經學習 Haskell 大約 4 個月了，我不得不說，學習曲線絕對很難（也很可怕：p）。
在解決了大約 15 道簡單的問題后，今天我轉到了 HackerRank https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem上的第一個中等難度問題。
這是 10 個測驗用例，我能夠通過其中的 6 個，但其余的都因超時而失敗，現在有趣的部分是，我已經可以看到一些具有提高性能潛力的部分，例如，我正在使用nub洗掉從 a 復制[Int]，但我仍然無法為演算法性能建立一個心理模型，不確定 Haskell 編譯器的主要原因會改變我的代碼以及懶惰在這里如何發揮作用。
import Data.List (nub)
getInputs :: [String] -> [String]
getInputs (_:r:_:p:[]) = [r, p]
findRating :: Int -> Int -> [Int] -> Int
findRating step _ [] = step
findRating step point (x:xs) = if point >= x then step else findRating (step 1) point xs
solution :: [[Int]] -> [Int]
solution [rankings, points] = map (\p -> findRating 1 p duplicateRemovedRatings) points
where duplicateRemovedRatings = nub rankings
main :: IO ()
main = interact (unlines . map show . solution . map (map read . words) . getInputs . lines)
GHCI 中的測驗用例
:l "solution"
let i = "7\n100 100 50 40 40 20 10\n4\n5 25 50 120"
solution i // "6\n4\n2\n1\n"
我的具體問題：
- 將
duplicateRemovedRankings變數計算一次，或者在地圖上的函式呼叫的每一次迭代。 - 就像在命令式編程語言中一樣，我可以使用某種列印機制來驗證上述問題，是否有某種與 Haskell 相同的等效方法。
- 根據我目前的理解，這個演算法的復雜度是，我知道
nub是O(n^2)findRating是O(n)getInputs是O(1)solution是O(n^2)
我該如何推理并建立績效的心理模型。
如果這違反了社區準則，請發表評論，我將洗掉此內容。感謝您的幫助 ：）
uj5u.com熱心網友回復：
首先，回答你的問題：
- 是的，
duplicateRemovedRankings只計算一次。沒有重復計算。 - 要除錯跟蹤，您可以使用
trace它的朋友（請參閱檔案以獲取示例和說明）。是的，它甚至可以在純非 IO 代碼中使用。但顯然，不要將它用于“正常”輸出。 - 是的，您對復雜性的理解是正確的。
現在，如何通過 HackerRank 的棘手測驗。
首先，是的，你是對的，nubO(N^2)。但是，在這種特殊情況下，您不必滿足于此。您可以利用排名預先排序的事實來獲得nub. 您所要做的就是跳過與下一個相同的元素：
betterNub (x:y:rest)
| x == y = betterNub (y:rest)
| otherwise = x : betterNub (y:rest)
betterNub xs = xs
這betterNub本身為您提供了 O(N) ，但對于 HackerRank 來說仍然不夠好，因為整體解決方案仍然是 O(N*M) - 對于每場比賽，您都在迭代所有排名。沒有布埃諾。
但在這里，你可以通過觀察排名是得到另一個改進排序，并在排序串列中搜索不一定是線性的。您可以改用二分搜索！
要做到這一點，您必須讓自己獲得恒定時間索引，這可以通過使用Array而不是串列來實作。
這是我的實作（請不要嚴厲判斷；我意識到我可能對邊緣情況進行了過度設計，但是嘿，它有效！）：
import Data.Array (listArray, bounds, (!))
findIndex arr p
| arr!end' > p = end' 1
| otherwise = go start' end'
where
(start', end') = bounds arr
go start end =
let mid = (start end) `div` 2
midValue = arr ! mid
in
if midValue == p then mid
else if mid == start then (if midValue < p then start else end)
else if midValue < p then go start mid
else go mid end
solution :: [[Int]] -> [Int]
solution [rankings, points] = map (\p -> findIndex duplicateRemovedRatings p 1) points
where duplicateRemovedRatings = toArr $ betterNub rankings
toArr l = listArray (0, (length l - 1)) l
有了這個，搜索本身得到 O(log N)，使整體解決方案 O(M * log N)。這對于 HackerRank 來說似乎已經足夠了。
（請注意，我將結果加 1 findIndex- 這是因為該練習需要基于 1 的索引）
uj5u.com熱心網友回復：
我相信 Fyodor 的回答非常適合您的前兩個半問題。對于后半部分，“我如何建立績效的心理模型？”，我可以說 SPJ 絕對是一位以聰明但無知的讀者可以理解的方式撰寫高技術論文的大師。實作書在庫存硬體上實作惰性功能語言非常出色，可以作為心理執行模型的基礎。還有 Okasaki 的論文，純函式資料結構，它討論了一種進行漸近復雜性分析的補充且顯著更高級別的方法。（實際上，我讀過他的書，其中顯然包含一些額外的內容，因此在自己決定此建議時請記住這一點。）
請不要被它們的長度嚇倒。我個人發現它們實際上很有趣。他們涵蓋的主題很大，無法壓縮為簡短/快速的答案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/316843.html
上一篇：Haskell中的通用模式