很难理解Haskell内存分配行为

Question

我偶然发现了Haskell和FP,并对这些可能性感到震惊.我内心的旧数学书呆子可以毫不费力地为实际有用的目的编写天真的代码.然而,尽管所有的阅读,我仍然很难理解如何不打出一些令人惊讶的性能瓶颈.

因此,我使用简单的实现编写了非常短的代码片段,然后尝试进行少量更改以查看性能如何响应.这里有一个我真的无法理解的例子......我写了这个函数,找到了约瑟夫斯问题的解决方案,目的是有一个天真的列表实现.

m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"

whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers

根据RTS,后者运行时间为190毫秒,生产率为63%.

然后我想要尝试的第一件事是删除(长度士兵-1)并用递减的整数替换它.

运行时间最长可达900毫秒,生产率降至16%,并且使用的内存比上述简单代码多47倍!所以我添加了严格的评估,强制使用Int类型,尝试删除全局变量等等,但没有多大帮助.我只是无法理解这种放缓.

m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"

whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left
                where left = take (n'-1) $ drop m $ cycle soldiers

我已经通过与绩效相关的文章和帖子进行了筛选,但我似乎并没有对此有任何暗示.仍然是一个Haskell noob我必须错过一些大的东西...这个如何添加参数(预先咀嚼的计算......)如此降低速度？

PS:我知道,如果约瑟夫斯真的和3000名士兵在一起,他们就不需要自杀......

Answer 1

第一个解决方案通过占用其长度来强制士兵列表的整个脊柱.第二种解决方案只强制(使用seq)士兵名单的头部.用a替换s left之间,你将恢复你的表现.seqlength left