haskell 函数的时间复杂度

Question

有没有一种简单的方法可以控制 haskell 中函数的时间复杂度？

我构建了一个函数来反转任何类型的列表，目标是使其具有线性时间复杂度，我试图这样解决：

rev :: [a] -> [a]
rev(x:[]) = [x]
rev(x:xs) = (rev xs) ++ [x]

我的意图是让它线性化，O(n)，但我不确定它是否确实如此，因此我想使用某种类型的工具来分析 code/function 以证明它实际上是线性。

因此我想知道：

这个函数是线性的吗？我可以用任何分析工具显示它吗？

Answer 1

(…) have it linear, O(n), but i am unsure if it actually is and would therefore like use some type of tool that might analyze the code/function to show that it is infact linear.

函数不是线性的。追加函数 (++) :: [a] -> [a] -> [a] 是线性的。因为我们对列表中的每个元素都这样做，所以我们最终得到 O(n²) 时间复杂度。

我们可以做的是使用 累加器 来使它成为线性函数：我们每次使用的额外参数都会以更新形式传递：

myrev :: [a] -> [a]
myrev = (`go` <b>[]</b>)
  where go (x:xs) <b>ys</b> = go xs (x:<b>ys</b>)
        go [] <b>ys</b> = <b>ys</b>

因此我们用一个空列表启动累加器。对于原始列表 x 中的每个元素，我们将其从第一个列表中弹出，并将其推入第二个列表。当第一个列表用完时，ys 包含反向列表。

Answer 2

使用 ghci 解释器：

作为粗略的第一步，您可以使用 ghci 解释器。为简单起见，让我们以交互方式而不是从源文件输入您对 rev 的定义。然后打开统计模式：

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help

 λ> 
 λ> let { rev :: [a] -> [a] ; rev [] = [] ; rev (x:xs) = (rev xs) ++ [x] }
 λ> 
 λ> :set +s
 λ>

然后我们只在 10,000 个元素和 20,000 个元素上对您的 rev 函数进行基准测试。对结果调用 length 的目的是强制进行完整评估：

 λ> 
 λ> length $ rev [1..10000]
10000
(1.27 secs, 4,294,492,504 bytes)
 λ> 
 λ> length $ rev [1..20000]
20000
(5.69 secs, 17,511,565,464 bytes)
 λ>

所以看起来工作量增加一倍会使成本增加大约 4 倍。 rev 函数具有二次成本。

为什么会这样？好吧，就像 Haskell 中的其他所有内容一样，运算符 (++) 最左边的参数是不可变的。因此，为了将其最左边的参数合并到其输出中，该函数必须复制它。

可以使用 Willem 的回答中提供的代码尝试相同的基准测试。好多了...为了获得有意义的数字，最好尝试使用 1,000,000 个元素而不是仅使用 10,000 个元素。

haskell 函数的时间复杂度

Time complexity for haskell function

performance

haskell

function

list

time-complexity

使用 ghci 解释器：