如何优化Haskell代码以通过HackerRank超时测试用例（练习用非竞赛）

问题1解答 #

duplicateRemovedRatings只会计算一次。Haskell中where子句绑定的变量，在当前作用域内被多次引用时，求值后的结果会被共享，不会重复计算。你这里该变量仅依赖固定的rankings输入，map迭代时复用的是同一个去重后的列表，不存在重复执行nub的开销。

问题2解答 #

可以用Debug.Trace模块的trace函数实现调试打印，效果和命令式语言的打印验证一致。你可以修改定义为：

import Debug.Trace (trace)
-- 其余代码不变
duplicateRemovedRatings = trace "执行了一次去重操作" $ nub rankings

运行程序时如果只输出一次执行了一次去重操作，就证明该变量仅计算一次。注意trace仅用于本地调试，不要在生产/提交代码中使用。

问题3解答 #

你的复杂度理解不完全准确：

• nub复杂度O(n²)、getInputs复杂度O(1)、单次findRating复杂度O(m)（m为去重后排名列表长度）的判断是对的
• 整体复杂度不是简单的O(n²)，还要加上查询的开销：假设查询分数的长度为k，那map遍历所有查询的开销是O(km)，整体复杂度为O(n² + km)。如果测试用例的n和k都很大，两部分开销都会触发超时。

Haskell性能认知模型建立方法 #

1. 先掌握惰性求值的核心规则：值仅在被需要时才求值，已经求值完成的结果会被共享。同一个作用域下绑定的无自由变量的变量，永远只会被求值一次，这是你判断会不会有重复计算的核心依据。
2. 记住基础库函数的复杂度：推导复杂度时先忽略编译器优化，按最高开销估算，再逐步考虑优化空间。比如有序列表去重要用O(n)的map head . group而不是O(n²)的nub，这类库函数的特性是你需要提前积累的常识。
3. 用工具验证性能猜测：不要靠脑补判断性能瓶颈，GHC自带完善的性能分析工具：编译时加上-prof -fprof-auto参数，运行程序时加上+RTS -p后缀，就能生成详细的性能报告，明确每个函数的时间、内存占比，定位瓶颈效率远高于人工推导。

本题的优化方向 #

你当前代码超时的核心原因有两个，修改后就能通过所有测试用例：

1. 替换nub去重：题目给出的排名是降序有序的，重复值全部相邻，用Data.List.group去重只要O(n)复杂度，替换为duplicateRemovedRatings = map head $ group rankings即可。
2. 替换线性查找为二分查找：findRating的线性遍历开销太高，去重后的排名是有序的，单次查找可以优化到O(logm)，整体查询开销从O(k*m)降到O(klogm)。如果利用题目中玩家分数递增的特性，用双指针法甚至能把查询开销降到O(k)。

内容的提问来源于stack exchange，提问作者vipulbhj