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

Question

我已经学习 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 中的测试用例

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)

我有具体问题：

• 该duplicateRemovedRankings变量将计算一次，还是在映射函数调用的每次迭代中计算。
• 就像在命令式编程语言中一样，我可以使用某种打印机制来验证上述问题，是否有一些等效的方法可以用 Haskell 来做同样的事情。
• 根据我目前的理解，这个算法的复杂度是，我知道nub是O(n^2)
  • findRating是O(n)
  • getInputs是O(1)
  • solution是O(n^2)

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

如果这违反了社区准则，请发表评论，我将删除它。感谢您的帮助 ：）

Answer 1

首先，回答您的问题：

1. 是的，duplicateRemovedRankings仅计算一次。无需重复计算。
2. 要调试跟踪，您可以使用trace及其朋友（请参阅文档以获取示例和说明）。是的，它甚至可以在纯非 IO 代码中使用。但显然，不要将其用于“正常”输出。
3. 是的，您对复杂性的理解是正确的。

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

首先，是的，你是对的，那nub就是 O(N^2)。然而，在这种特殊情况下，您不必满足于此。您可以利用排名预先排序的事实来获得 的线性版本nub。您所要做的就是在元素等于下一个元素时跳过它们：

betterNub (x:y:rest) 
  | x == y = betterNub (y:rest)
  | otherwise = x : betterNub (y:rest)
betterNub xs = xs

这本身为您提供了 O(N) betterNub，但对于 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 的索引）