用于分析Haskell程序性能的工具
在解决一些项目欧拉问题来学习Haskell（所以目前我是一个完全初学者），我来到问题13 。 我写了这个（天真的）解决scheme：
--Get Number of Divisors of n numDivs :: Integer -> Integer numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 --Generate a List of Triangular Values triaList :: [Integer] triaList = [foldr (+) 0 [1..n] | n <- [1..]] --The same recursive triaList2 = go 0 1 where go cs n = (cs+n):go (cs+n) (n+1) --Finds the first triangular Value with more than n Divisors sol :: Integer -> Integer sol n = head $ filter (\x -> numDivs(x)>n) triaList2 这个解决schemen = 500（sol 500）极其缓慢（现在运行了2个多小时），所以我想知道如何找出这个解决scheme为什么这么慢。 有没有什么命令可以告诉我大部分的计算时间是花在什么地方，所以我知道我的haskell程序的哪个部分很慢？ 就像一个简单的分析器。
为了说清楚，我并不是要求更快的解决scheme，而是寻求解决scheme。 如果你没有Haskell知识，你将如何开始？
我试图写两个triaList函数，但没有办法testing哪一个更快，所以这就是我的问题开始。
谢谢
如何找出为什么这个解决scheme如此缓慢。 有没有什么命令可以告诉我大部分的计算时间是花在什么地方，所以我知道我的haskell程序的哪个部分很慢？
恰恰！ GHC提供了许多优秀的工具，包括：
- 运行时统计
- 时间分析
- 堆分析
- 线程分析
- 核心分析。
- 比较基准
- GC调谐
关于使用时间和空间分析的教程是真实世界Haskell的一部分 。
GC统计
首先，确保你用ghc -O2编译。 你可以确定它是一个现代的GHC（例如GHC 6.12.x）
我们能做的第一件事是检查垃圾收集是不是问题。 用+ RTS -s运行你的程序
$ time ./A +RTS -s ./A +RTS -s 749700 9,961,432,992 bytes allocated in the heap 2,463,072 bytes copied during GC 29,200 bytes maximum residency (1 sample(s)) 187,336 bytes maximum slop **2 MB** total memory in use (0 MB lost due to fragmentation) Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 13.15s ( 13.32s elapsed) GC time 0.11s ( 0.15s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 13.26s ( 13.47s elapsed) %GC time **0.8%** (1.1% elapsed) Alloc rate 757,764,753 bytes per MUT second Productivity 99.2% of total user, 97.6% of total elapsed ./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total
这已经给我们提供了很多信息：你只有2M的堆，而GC占用了0.8％的时间。 所以不用担心分配问题。
时间档案
为您的程序获取时间档案非常简单：使用-prof -auto-all进行编译
$ ghc -O2 --make A.hs -prof -auto-all [1 of 1] Compiling Main ( A.hs, Ao ) Linking A ...
而且，对于N = 200：
$ time ./A +RTS -p 749700 ./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total
创build一个文件A.prof，其中包含：
Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final) A +RTS -p -RTS total time = 13.18 secs (659 ticks @ 20 ms) total alloc = 4,904,116,696 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc numDivs Main 100.0 100.0
表明你所有的时间都花在了numDivs上，也是你所有分配的来源。
堆configuration文件
您也可以通过运行+ RTS -p -hy（创buildA.hp，通过将其转换为后记文件（hp2ps -c A.hp）来查看）来分解这些分配，从而生成：
这告诉我们你的内存使用没有任何问题：它在不变的空间分配。
所以你的问题是numDivsalgorithm的复杂性：
toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2
解决这个问题，这是你运行时间的100％，其他一切都很简单。
优化
这个expression式是stream融合优化的一个很好的候选者，所以我会重写它来使用Data.Vector ，就像这样：
numDivs n = fromIntegral $ 2 + (U.length $ U.filter (\x -> fromIntegral n `rem` x == 0) $ (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))
这应该融合成一个单一的循环，没有不必要的堆分配。 也就是说，它比列表版本具有更好的复杂性（通过不变的因素）。 您可以使用ghc-core工具（对于高级用户）来优化后检查中间代码。
testing这个，ghc -O2 – 制作Z.hs
$ time ./Z 749700 ./Z 3.73s user 0.01s system 99% cpu 3.753 total
所以它将运行时间缩短了3.5倍，而不改变algorithm本身。
结论
你的问题是numDivs。 这是你运行时间的100％，并且具有非常复杂的可怕性。 想一想numDivs，以及如何为你生成N个N的每个N。 尝试记忆，因为值不会改变。
为了测量哪些函数更快，可以考虑使用标准 ，这将提供关于运行时间的亚微秒级改进的统计学上可靠的信息。
附加物
由于numDivs是你运行时间的100％，所以触摸程序的其他部分不会有太大的差别，但是为了教学目的，我们也可以用stream融合来重写。
我们也可以重写trialList，并依靠融合把它变成你在trialList2中手工编写的循环，它是一个“前缀扫描”函数（aka scanl）：
triaList = U.scanl (+) 0 (U.enumFrom 1 top) where top = 10^6
同样对于sol：
sol :: Int -> Int sol n = U.head $ U.filter (\x -> numDivs x > n) triaList
与整体运行时间相同，但代码更简洁一些。
Dons的答案很好，没有通过直接解决问题而成为一个破坏者。
在这里我想提出一个我最近写的一个小工具 。 当您需要比默认的ghc -prof -auto-all更详细的configuration文件时，它可以节省您手动编写SCC批注的时间。 除此之外，它是多彩的！
下面是你给出的代码（*）的例子，绿色是好的，红色是慢的： 
一直在创build除数列表。 这表明你可以做一些事情：
1.更快地过滤n rem x == 0 ，但由于它是一个内置函数，所以它可能已经很快了。
2.创build一个较短的列表。 你已经在这个方向上做了一些事情，只检查最多n quot 2 。
3.完全丢弃列表生成，并使用一些math来获得更快的解决scheme。 这是项目欧拉问题的常用方法。
（*）我把这个代码放在一个名为eu13.hs的文件中，添加一个主函数main = print $ sol 90 。 然后运行visual-prof -px eu13.hs eu13 ，结果在eu13.hs.html 。
Haskell相关说明： triaList2当然比triaList快，因为后者执行了大量不必要的计算。 它将花费二次时间来计算triaList第一个元素，但对triaList2线性的。 还有另外一个优雅（而且有效）的方法来定义一个三angular形数字的无限懒惰列表：
triaList = 1 : zipWith (+) triaList [2..]
math相关的注意事项：没有必要检查所有除数到n / 2，只要检查sqrt（n）就足够了。
您可以使用标志运行程序以启用时间分析。 像这样的东西：
./program +RTS -P -sprogram.stats -RTS
这应该运行程序并生成一个名为program.stats的文件，这将花费多less时间在每个函数中。 您可以在GHC 用户指南中find更多关于GHC分析的信息。 对于基准testing，有Criterion库。 我发现这个博客文章有一个有用的介绍。
