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需要40秒.在一个非常快的工作站上.评估aLotOfCombinationsOfCombinations!! 0花了2天:-(

我怎样才能加快这段代码的速度？到目前为止,我有两个想法 - 使用分析器.myapp +RTS -sstderr在使用GHC编译后尝试运行,但得到一个空白的屏幕,并且不想等待它完成的几天.

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

Answer 1

使用-fforce-recomp,-O2和-fllvm标志

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

描述您的代码

该-sstderr标志是不完全剖析.当人们说分析时,他们通常会谈论堆分析或时间分析-prof和-auto-all标记.

避免昂贵的原语

如果您需要内存中的整个列表(即它不会被优化掉),那么请考虑未装箱的向量.如果Int不这样做Integer,请考虑(但是当你不知道时,Integer是一个合理的默认值!).在正确的时间使用工人/包装变换.如果您严重依赖Data.Map,请尝试使用Data.HashMap无序容器库.这个列表可以继续,但由于你还没有直觉知道你的计算时间在哪里,所以应该首先进行分析!