衡量绩效的一种方法

Question

鉴于99 Haskell问题的练习14 :

(*)复制列表的元素.

例如.:

*Main> dupli''' [1..10]
[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]

我已经实施了4个解决方案:

{-- my first attempt --}
dupli :: [a] -> [a]
dupli [] = []
dupli (x:xs) = replicate 2 x ++ dupli xs

{-- using concatMap and replicate --}
dupli' :: [a] -> [a]
dupli' xs = concatMap (replicate 2) xs

{-- usign foldl --}
dupli'' :: [a] -> [a]
dupli'' xs = foldl (\acc x -> acc ++ [x,x]) [] xs

{-- using foldl 2 --}
dupli''' :: [a] -> [a]
dupli''' xs = reverse $ foldl (\acc x -> x:x:acc) [] xs

不过,我不知道如何真正衡量绩效.

那么在性能方面推荐的功能(来自上面的列表)是什么.

有什么建议 ？

Answer 1

这些看起来都比他们需要的更复杂(和/或效率更低).为什么不这样:

dupli [] = []
dupli (x:xs) = x:x:(dupli xs)

您的最后一个示例接近于基于折叠的良好实现,但您应该使用foldr,这将消除反转结果的需要:

dupli = foldr (\x xs -> x:x:xs) []

至于衡量绩效,"经验方法"是分析.随着Haskell程序规模的扩大,它们在运行时和空间复杂性方面可能会相当难以推理,并且分析是最好的选择.此外,在衡量两个函数的相对复杂性时,粗略但经常有效的经验方法是简单地比较它们对一些足够大的输入所花费的时间; 例如,花费多长时间length $ dupli [1..1000000]并将其与之比较dupli''等.

但对于一个程序这么小,根据你对所讨论的数据结构的知识 - 在这种情况下,列表 - 来计算算法的运行时复杂性应该不会太难.这里有一个提示:每次使用concatenation(x ++ y)时,运行时复杂度都是O(length x).如果在对大小为n的列表的所有元素进行操作的递归算法中使用连接,则基本上将具有O(n ^ 2)算法.我给出的两个例子和你的最后一个例子都是O(n),因为在递归定义中使用的唯一操作(:)是O(1).

Answer 2

建议您使用标准包.一个很好的描述是http://www.serpentine.com/blog/2009/09/29/criterion-a-new-benchmarking-library-for-haskell/.

要在此汇总并使其适应您的问题,以下是步骤.安装标准

cabal install criterion -fchart

然后将以下内容添加到您的代码中

import Criterion.Main

l = [(1::Int)..1000]

main = defaultMain [ bench "1" $ nf dupli l
                   , bench "2" $ nf dupli' l 
                   , bench "3" $ nf dupli'' l
                   , bench "4" $ nf dupli''' l
                   ]

您需要nf以强制评估整个结果列表.否则你只会获得计算的thunk.

之后编译并运行

ghc -O --make dupli.hs
./dupli -t png -k png

并且您可以获得不同功能的运行时间的漂亮图表.

事实证明,这dupli'''是你的功能中最快的,但是所foldr列出的那个版本比所有人都要好.