algorithm - 如何优化 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 及其 friend (有关示例和解释，请参阅文档)。是的，它甚至可以在纯的非 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 的索引)