Haskell中两种SSD最大值选择算法哪一种运行速度更快？

你的猜测是对的，第一种maxSSD的运行速度确实远快于第二种，具体原因和验证方法如下：

性能差距的核心原因 #

• 第一种maxSSD是尾递归实现：递归调用是每步逻辑的最后一个操作，GHC（Haskell编译器）会自动把这种逻辑优化成循环结构，遍历列表的全程只需要常数级的栈空间，整个列表只需要遍历1次，时间复杂度稳定为O(n)。
• 第二种maxSSD'存在笔误：你提供的代码里，maxSSD'的所有实现子句都错写成了maxSSD，修正后它是普通递归实现，每一步都要先递归求出剩余列表的最大值，才能和当前SSD的容量做比较。这种实现不仅会占用O(n)级别的栈空间，列表长度过大时甚至会栈溢出，而且每一步都要重复遍历列表的后缀，最坏时间复杂度可达O(n²)，列表越长和第一种的性能差距就越明显。

验证方法 #

你可以用两种简单的方法直观验证性能差异：

• 在GHCi中测试：输入:set +s开启耗时和内存统计，构造一个包含上万条SSD数据的列表，分别调用两个函数看执行耗时和内存占用，差距会非常明显。
• 看编译后的核心代码：给GHC加上-ddump-simpl参数编译代码，你会看到第一种maxSSD被优化成了高效的循环结构，第二种还是多层递归调用的结构。

另外额外提一下两个函数的逻辑差异：第一种无SSD时返回传入的初始值-1，第二种无SSD时返回0，你可以根据自己的业务需要调整边界值。

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