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

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)

如何推理和建立性能的心理模型。

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

- vipulbhj

---

回答简单的问题：一次，和 Debug.Trace.trace。 - David Eisenstat

“nub” 很糟糕，只在你预先知道非常小的列表上使用它。 - leftaroundabout

使用 containers 包中的 Data.IntSet 和 Data.Map.Strict，时间复杂度降至 min(n * log n, m)，其中 n 是 ranked 的长度，m 是 player 的长度。 - user1984

@user1984 你是不是想说 min(n * log n, m * log n)？我们使用列表可以得到 O(n+m)，这可能更好。我在下面的评论中描述了它。（除非我漏掉了什么） - Will Ness

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

这使得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 的索引）

- Fyodor Soikin

---

为什么要这样做？描述中指出：“玩家的分数player按升序排列。”（强调是我的）。我们只需要在排行榜排名列表ranked上向前滚动，将其反转并转换为RLE格式，直到达到第一个玩家的分数；然后随着我们的游戏越来越多，我们通过弹出头元素来可能更新当前头条目的方式将其向后滚动。reverse&rle和toArray的时间复杂度均为O(n)。弹出操作的总成本为O(m+n)。我有什么遗漏吗？ - Will Ness

哦，我完全忽略了球员也是有序的这一事实。嗯...不过，即使 O(M * log N)，仍然通过了所有测试。 - Fyodor Soikin

betterNub = map head . group - leftaroundabout

是的，但我想展示这个想法以及它如何工作。 - Fyodor Soikin

Answer 2

我认为Fyodor的回答对于你前两个问题非常好。而对于最后半个问题：“如何建立性能的心理模型？”，我可以说SPJ是在高度技术文章中以易懂方式展现方面的绝对大师。他的实现书“在通用硬件上实现惰性函数语言”是很好的，可以作为一个心理执行模型的基础。此外，还有Okasaki的论文，“纯函数数据结构”，它讨论了一种互补且显著更高级的方法来进行渐进复杂度分析。 (实际上，我读了他的书，它显然包括一些额外内容，所以在自行决定时请注意。) 请不要因它们的长度而感到畏惧。我个人觉得阅读它们实际上是很有趣的；而且它们涵盖的主题是很大的，无法被简短/快速回答。

- Daniel Wagner

---

点赞只是因为称赞我的回答很好。我非常自恋 :-) - Fyodor Soikin