如何优化 Haskell 代码以通过 HackerRanks 超时测试用例（不适用于任何正在进行的比赛，只是我练习）

Question

我已经学习 Haskell 大约 4 个月了，我不得不说，学习曲线肯定很难（也很可怕 :p）。

在解决了大约 15 个简单的问题后，今天我转向了我在 HackerRank 上的第一个中等难度问题 https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem。

这是 10 个测试用例，我能够通过其中的 6 个，但其余的都因超时而失败，现在有趣的部分是，我已经可以看到一些具有性能提升潜力的部分，例如，我正在使用 nub 从 [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 变量会被计算一次，还是在 map 函数调用的每次迭代中计算。
就像在命令式编程语言中一样，我可以使用某种打印机制来验证上述问题，是否有一些等效的方法可以用 Haskell 做同样的事情。
按照我目前的理解，这个算法的复杂度应该是，我知道nub是O(n^2)
- findRating 是 O(n)
- getInputs 是 O(1)
- solution 是 O(n^2)

我该如何推理并建立绩效心理模型。

如果这违反了社区准则，请发表评论，我会删除它。谢谢你的帮助:)

Answer 1

先，回答你的问题：

是的，duplicateRemovedRankings 只计算了一次。没有重复计算。
要调试跟踪，您可以使用 trace 及其朋友（有关示例和解释，请参阅文档）。是的，它甚至可以用在纯非 IO 代码中。但显然，不要将它用于“正常”输出。
是的，您对复杂性的理解是正确的。

现在，如何通过 HackerRank 的棘手测试。

首先，是的，你是对的 nub 是 O(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 来说似乎已经足够好了。

（请注意，我在 findIndex 的结果中加 1 - 这是因为练习需要基于 1 的索引）

Answer 2

我相信 Fyodor 的回答非常适合您的前两个半问题。对于后半部分，“我如何为绩效建立心智模型？”，我可以说 SPJ 绝对是一位以聪明但无知的人可以理解的方式撰写高技术论文的大师 reader。实施书 Implementing lazy functional languages on stock hardware is excellent and can serve as the basis of a mental execution model. There is also Okasaki's thesis, Purely functional data structures，其中讨论了进行渐近复杂性分析的一种互补且显着更高级别的方法。（实际上，我读过他的书，其中显然包含一些额外的内容，所以在决定此推荐时请记住这一点。）

请不要被它们的长度吓倒。我个人发现它们实际上读起来很有趣；他们涵盖的主题很大，无法压缩为 short/quick 个答案。

如何优化 Haskell 代码以通过 HackerRanks 超时测试用例（不适用于任何正在进行的比赛，只是我练习）

How to optimise Haskell code to pass HackerRanks timed out test cases (Not for any ongoing competition, just me practicing)

algorithm

haskell

haskell-platform