难以理解的Haskell内存分配行为

我偶然发现了Haskell和FP，并被可能性吓倒了。我内心的老数学书呆子没有任何困难写实际有用的朴素代码。尽管如此，我仍然很难理解如何避免出现一些令人惊讶的性能瓶颈。难以理解的Haskell内存分配行为

所以我写了很简短的代码与天真的实现，然后尝试一些改变，看看性能如何响应。这里有一个例子，我真的无法理解......我写了这个函数，它找到了一个解决方案Josephus problem,目的与一个天真的列表实现。

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

后者运行时间为190 ms，根据RTS的生产率为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名士兵，他们就不会需要自杀......

来源

2011-08-30 Mathias Dolidon

没有必要seq n'，whosLeft在n'中已经很严格。但你应该优化编译。 – augustss

第一个解决方案利用其长度迫使士兵名单的整个脊椎。第二个解决方案只强制（使用seq）士兵列表的头。将left替换为seq与length left之间的内容，然后重新开始。

来源

2011-08-30 18:13:06 sclv

令人惊叹。所以我完全错过了这个观点，毕竟它很简单：D非常感谢你sclv。这是一个有趣的技巧要知道。 –

这是[deepseq]（http://hackage.haskell.org/package/deepseq）软件包的优点之一吗？ –

@Antal：我不喜欢使用deepseq，因为它是一个钝器。例如，在这种情况下，您只需强制列表的脊椎。 Deepseq也强制使用这些值。它相对便宜，因为它们本质上已经被迫，但是成本很低，如果你将其乘以列表的长度和递归调用的数量，它就会相加。如果你急着想，Deepseq很好，但我认为如果可能的话，以最佳方式混合懒惰和严谨，强迫它在操作上更合理，而不是无差别。 – sclv

难以理解的Haskell内存分配行为

回答

相关问题