Haskell:无法理解瓶颈

Question

我解决了Project Euler问题,然后用Haskell维基上的问题面对我的解决方案.他们非常相似,但是我的时间是7.5秒,而另外0.6!我把它们都编成了.

我看起来如下:

main = print . maximumBy (compare `on` cycleLength) $ [1..999]
        where cycleLength d = remainders d 10 []

和其中一个维基:

main = print . fst $ maximumBy (comparing snd) [(n, cycleLength n) | n <- [1..999]]
        where cycleLength d = remainders d 10 []

我也尝试改变compare `on`,comparing cycleLength但性能保持不变.
因此,我必须得出结论,所有差异都在于计算运行中的值与在列表理解中进行转换.

虽然时间上的差异非常大:第二个版本的速度提升了12.5倍!

Answer 1

该maximumBy函数将多次重复检查列表中的相同数字 - 每次检查一个数字时,都必须重新计算 cycleLength.这是一项昂贵的操作!

因此,wiki算法使用称为decorate-sort-undecorate的技术.现在,在这里你没有排序,但它足够接近.你首先预先计算cycleLength所有数字的值,(即你做一个'缓存'),然后你做最大的操作,然后你解开它们(使用fst.)这样,你节省了很多计算!

编辑:为了说明它,看一下源代码中的maximumBy函数Data.List:

-- | The 'maximumBy' function takes a comparison function and a list
-- and returns the greatest element of the list by the comparison function.
-- The list must be finite and non-empty.
maximumBy               :: (a -> a -> Ordering) -> [a] -> a
maximumBy _ []          =  error "List.maximumBy: empty list"
maximumBy cmp xs        =  foldl1 maxBy xs
                        where
                           maxBy x y = case cmp x y of
                                      GT -> x
                                      _  -> y

它在2的窗口中移动; 请求每个号码(在您的情况下计算)两次.这意味着对于999次迭代,您的版本将调用cycleLength d1996次(n*2-2),而wiki版本将调用它999(n)次.

这并不能解释完全延迟 - 只有2倍,但因子更接近于10.

这是您的版本的配置文件,

COST CENTRE entries %time %alloc %time %alloc MAIN 0 0.0 0.0 100.0 100.0 CAF 0 0.0 0.0 100.0 100.0 main 1 0.0 0.0 100.0 100.0 f 1 0.0 0.0 100.0 100.0 maximumBy 1 0.0 0.0 100.0 99.9 maximumBy.maxBy 998 0.0 0.1 100.0 99.9 cycleLength 1996 0.1 0.2 100.0 99.8 remainders 581323 99.3 94.4 99.9 99.7 remainders.r' 581294 0.7 5.2 0.7 5.2

和维基版本:

COST CENTRE entries %time %alloc %time %alloc MAIN 0 0.0 0.0 100.0 100.0 CAF 0 0.0 0.0 100.0 99.9 main 1 0.0 0.1 100.0 99.9 f' 1 0.0 0.8 100.0 99.8 cycleLength 999 0.2 0.5 100.0 98.6 remainders 95845 98.3 93.0 99.8 98.2 remainders.r' 95817 1.5 5.2 1.5 5.2 maximumBy 1 0.0 0.1 0.0 0.4 maximumBy.maxBy 998 0.0 0.2 0.0 0.2

看看这里的配置文件,你的版本似乎经历了更多的分配(大约10到12倍),但总体上没有使用更多的RAM.因此,我们需要根据分配来解释累积因子5或6.

剩余是递归的.在您的示例中,它被称为581294次.在wiki示例中,它被调用了95817次.我们增加了5-6倍!

所以我认为compare这里的电话也是一个问题.因为它适用cycleLength于我们想要比较的两件事!在wiki问题中,cycleLength应用到每个数字,但是在这里,我们将它应用于每个数字两次,并且比较似乎更频繁地应用,并且这是一个问题,尤其是对于更大的数字,因为remainders具有不好的复杂性(它似乎呈指数级,但我不确定.)

由于两个程序的最大内存消耗并没有那么显着不同,我认为这与堆没有任何关系.