performance - Haskell - 缓存函数调用的简单方法

Question

我有这样的功能:

millionsOfCombinations = [[a, b, c, d] | 
  a <- filter (...some filter...) someListOfAs, 
  b <- (...some other filter...) someListOfBs, 
  c <- someListOfCs, d <- someListOfDs]

aLotOfCombinationsOfCombinations = [[comb1, comb2, comb3] | 
  comb1 <- millionsOfCombinations, 
  comb2 <- millionsOfCombinations,
  comb3 <- someList,
  ...around 10 function calls to find if
    [comb1, comb2, comb3] is actually useful]

评估 millionsOfCombinations需要40s。在一个非常快的工作站上。评估 aLotOfCombinationsOfCombinations !!0 花了 2 天 :-(

如何加快此代码的速度？到目前为止，我有 2 个想法 - 使用分析器。尝试运行 myapp +RTS -sstderr用 GHC 编译后，但得到一个空白屏幕，不想等待几天才能完成。

第二个想法是以某种方式缓存 millionsOfCombinations .我是否正确理解 aLotOfCombinationsOfCombinations 中的每个值？ , millionsOfCombinations被多次评估？如果是这样，我该如何缓存结果？显然我刚刚开始学习 Haskell。我知道有一种方法可以使用 monad 进行调用缓存，但我仍然不明白这些东西。

Answer 1

使用 -fforce-recomp , -O2和 -fllvm旗帜

如果您还没有，请务必使用上述标志。我通常不会提及它，但我最近看到一些不知道强大优化不是默认设置的问题。

配置您的代码
-sstderr flag 不完全是分析。当人们说分析时，他们通常是通过 -prof and -auto-all 谈论堆分析或时间分析。标志。

避免使用昂贵的原语

如果您需要内存中的整个列表(即它不会被优化掉)，那么请考虑未装箱的向量。如果 Int将代替Integer ，考虑一下(但是当您不知道时，整数是一个合理的默认值!)。在正确的时间使用 worker /包装转换。如果你严重依赖 Data.Map , 尝试使用 Data.HashMap来自无序容器库。这个列表可以继续下去，但是由于您还没有直觉知道计算时间的去向，分析应该首先出现!