8

假设我被赋予了两个功能：

f :: [a] -> b
g :: [a] -> c

我想编写一个与此等效的函数：

h x = (f x, g x)

但是当我这样做时，对于大型列表，我不可避免地会耗尽内存。

一个简单的例子如下：

x = [1..100000000::Int] 
main = print $ (sum x, product x)

我理解是这种情况，因为列表x被存储在内存中而没有被垃圾收集。它会更好，而不是f在g“x并行”中工作。

假设我不能更改fand g，也不想制作一个单独的副本x（假设x生产成本很高），我该如何编写h而不遇到内存不足的问题？

4

3 回答 3

12

一个简短的回答是你不能。由于您无法控制fand g，因此您无法保证函数按顺序处理其输入。这样的函数也可以在产生最终结果之前将整个列表存储在内存中。

但是，如果你的函数表示为折叠，情况就不同了。这意味着我们知道如何逐步应用每个步骤，因此我们可以在一次运行中并行化这些步骤。

关于这个领域的资源很多。例如：

使用具有正确定义的空间边界的一系列值的模式更普遍地解决了管道类库，如管道、迭代或管道。例如，在管道中，您可以将计算总和和乘积的组合表示为

import Control.Monad.Identity
import Data.Conduit
import Data.Conduit.List (fold, sourceList)
import Data.Conduit.Internal (zipSinks)

product', sum' :: (Monad m, Num a) => Sink a m a
sum'     = fold (+) 0
product' = fold (*) 1

main = print . runIdentity $ sourceList (replicate (10^6) 1) $$
                                zipSinks sum' product'
于 2013-06-05T08:08:18.577 回答
2

如果您可以将函数转换为折叠，则可以将它们与扫描一起使用：

x = [1..100000000::Int] 
main = mapM_ print . tail . scanl foo (a0,b0) . takeWhile (not.null)  
         . unfoldr (Just . splitAt 1000)  -- adjust the chunk length as needed
         $ x

foo (a,b) x = let a2 = f' a $ f x ; b2 = g' b $ g x
              in a2 `seq` b2 `seq` (a2, b2)

f :: [t] -> a         -- e.g. sum
g :: [t] -> b         --      (`rem` 10007) . product
f' :: a -> a -> a     -- e.g. (+)
g' :: b -> b -> b     --      ((`rem` 10007) .) . (*)

我们以块的形式使用输入以获得更好的性能。用 编译-O2，这应该在一个恒定的空间中运行。打印中期结果作为进度的指示。

如果你不能把你的函数变成一个折叠，这意味着它必须消耗整个列表来产生任何输出，这个技巧不适用。

于 2013-06-05T09:34:39.757 回答
2

您可以使用多个线程来f x并行评估g x。

例如

x :: [Int]
x = [1..10^8]

main = print $ let a = sum x
                   b = product x
               in a `par` b `pseq` (a,b)

这是利用 GHC 的并行运行时通过同时做两件事来防止空间泄漏的好方法。

或者，您需要融合f并g进入一次 pass。

于 2013-06-05T07:53:37.293 回答