19

我的背景是生物信息学，尤其是下一代测序，但问题是通用的；所以我将以一个日志文件为例。

该文件非常大（千兆字节大，已压缩，因此无法放入内存），但易于解析（每一行都是一个条目），因此我们可以轻松编写如下内容：

parse :: Lazy.ByteString -> [LogEntry]

现在，我想从日志文件中计算出很多统计数据。编写单独的函数是最简单的，例如：

totalEntries = length
nrBots = sum . map fromEnum . map isBotEntry
averageTimeOfDay = histogram . map extractHour

所有这些都是形式foldl' k z . map f。

问题是，如果我尝试以最自然的方式使用它们，比如

main = do
    input <- Lazy.readFile "input.txt"
    let logEntries = parse input
        totalEntries' = totalEntries logEntries
        nrBots' = nrBots logEntries
        avgTOD = averageTimeOfDay logEntries
    print totalEntries'
    print nrBots'
    print avgTOD

这将在内存中分配整个列表，这不是我想要的。我希望折叠同步完成，以便可以对 cons 单元进行垃圾收集。如果我只计算一个统计数据，就会发生这种情况。

我可以编写一个大函数来执行此操作，但它是不可组合的代码。

或者，这就是我一直在做的，我分别运行每个通道，但这每次都会重新加载和解压缩文件。

4

2 回答 2

11

这是对 sdcvvc 的评论的评论，指的是这篇“漂亮的折叠”文章 太酷了——正如他所说，很漂亮——我无法抗拒添加实例Functor和Applicative其他一些现代化。比如说，同时折叠x y和z是一个简单的产品：(,,) <$> x <*> y <*> z. 我制作了一个 0.5GB 的小随机整数文件，在我生锈的笔记本电脑上计算长度、总和和最大值花了 10 秒。进一步的注释似乎没有帮助，但是编译器可以看到Int我感兴趣的全部内容；显而易见map read . lines的解析器导致了一场无望的空间和时间灾难，所以我粗暴地使用ByteString.readInt; 否则它基本上是一个Data.List过程。

{-# LANGUAGE GADTs, BangPatterns #-}

import Data.List (foldl', unfoldr)
import Control.Applicative 
import qualified Data.ByteString.Lazy.Char8 as B

main = fmap readInts (B.readFile "int.txt") >>= print . fold allThree
  where allThree = (,,) <$> length_ <*> sum_ <*> maximum_

data Fold b c where  F ::  (a -> b -> a) -> a -> (a -> c) -> Fold b c
data Pair a b = P !a !b

instance Functor (Fold b) where  fmap f (F op x g) = F op x (f . g)

instance Applicative (Fold b) where
  pure c = F const () (const c)
  (F f x c) <*> (F g y c') = F (comb f g) (P x y) (c *** c')
    where comb f g (P a a') b = P (f a b) (g a' b)
          (***) f g (P x y) = f x ( g y)

fold :: Fold b c -> [b] -> c
fold (F f x c) bs = c $ (foldl' f x bs)

sum_, product_ :: Num a => Fold a a
length_ :: Fold a Int
sum_     = F (+) 0 id
product_ = F (*) 1 id
length_  = F (const . (+1)) 0 id
maximum_ = F max 0 id
readInts  = unfoldr $ \bs -> case B.readInt bs of
  Nothing      -> Nothing
  Just (n,bs2) -> if not (B.null bs2) then Just (n,B.tail bs2) 
                                      else Just (n,B.empty)

编辑：不出所料，因为我们必须处理上面的未装箱类型，并且从例如 2G 文件派生的未装箱矢量可以放入内存中，如果给数据明显重新编码，这一切都快两倍并且表现得更好。 Vector.Uboxed http://hpaste.org/69270 当然，这与具有像 Note 这样的类型无关，LogEntry 尽管Fold类型和折叠“乘法”在没有修改的情况下推广到顺序类型，因此例如与Chars上的操作相关联的折叠或Word8s 可以同时直接折叠在 ByteString 上。必须首先定义 a foldB，通过重新定义在各种 ByteString 模块中fold使用s 。foldl'但是Folds 和产品Folds 与折叠Chars 或Word8s的列表或向量相同

于 2012-05-30T04:47:47.340 回答
11

要多次处理惰性数据，在恒定空间中，您可以做三件事：

  • 从头开始重新构建惰性列表n次
  • fuse n进入单个顺序折叠，在锁定步骤中执行每个步骤。
  • 用于par同时进行n次并行遍历

这些是你的选择。最后一个是最酷的:)

于 2012-05-29T16:45:02.817 回答