haskell - 找出 Haskell 函数的复杂性

Question

如何找到不同 Haskell 函数的复杂性(以 big-O 表示)？

例如， subsequences 的复杂度是多少？ ?

Answer 1

您只能通过查看代码来计算函数的确切复杂度。但是，您可以使用 criterion 进行估算。 .

例如，下面的程序估计 subsequence 的复杂度作为列表长度的函数。

module Main where

import Criterion (bench, nf)
import Criterion.Main (defaultMain)
import Data.List (subsequences)
import Control.DeepSeq (deepseq)

main = defaultMain (map createBenchmark [0, 2 .. 24])
    where
        createBenchmark n =
            let
                xs = replicate n 'x'
            in
                xs `deepseq` (bench (show n) $ nf subsequences xs)

如果你编译它(使用 -O2 !)并运行它

./Main -u report

(或者

./Main --csv report

在较新版本的标准中)

您将获得一个包含数据的 CSV 文件(平均时间、方差和每次运行的其他信息)。

如果您绘制该数据，您会发现它在 n 中是指数的。如以下 gnuplot session 所示。

> f(x) = a * exp(b * x)
> fit f(x) 'report' using ($0 * 2):2 every ::2 via a,b
...

Final set of parameters            Asymptotic Standard Error
=======================            ==========================

a               = 1.7153e-07       +/- 5.441e-09    (3.172%)
b               = 0.711104         +/- 0.001438     (0.2023%)


correlation matrix of the fit parameters:

               a      b      
a               1.000 
b              -1.000  1.000
> set log y
> set xlabel 'n'
> set ylabel 'mean time [s]'
> plot 'report' using ($0 * 2):2 every ::2 with lp title 'data', f(x) title 'fit'

a大约为零， b几乎没有错误。所以可以肯定地猜测复杂度是 O(2^n)，因为 e^0.71 几乎正好是 2。

当然，这种技术假定您实际上正在使用函数返回的所有内容。如果您只访问返回列表的第一个元素，由于延迟评估，复杂度将为 O(1)。

您可能会找到一种方法使该程序独立于要进行基准测试的函数(至少对于仅采用列表的函数)。还有一些不错的 Haskell 库用于绘制数据，因此您无需依赖外部程序(不幸的是，作为一名科学家，我除了 gnuplot 从未使用过任何东西)。