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セルをガベージコレクションできるように、フォールドを同期的に実行する必要があります。統計を1つだけ計算すると、これが起こります。

これを行う大きな関数を1つ書くことはできますが、それは構成不可能なコードです。

または、これまで行ってきたことですが、各パスを個別に実行しますが、これにより、毎回ファイルが再ロードおよび解凍されます。

4

2 に答える 2

11

怠惰なデータを複数回処理するには、一定のスペースで次の3つのことを実行できます。

  • レイジーリストを最初からn回再構築する
  • ヒューズnは、ロックステップで各ステップを実行する単一の連続した折り畳みに渡されます。
  • 同時にn個の並列トラバーサルを実行するために使用parします

それらはあなたの選択肢です。最後のものは最もクールです:)

于 2012-05-29T16:45:02.817 に答える
11

この「美しい折りたたみ」エッセイを参照しているsdcvvcのコメントに対するこのコメント それはとてもクールでした-彼が言うように美しい-私は追加FunctorとApplicativeインスタンスと他のいくつかの近代化に抵抗できませんでした。x yたとえば、の同時折りたたみzは、簡単な製品です(,,) <$> x <*> y <*> z。私は小さなランダムなintの0.5ギガバイトのファイルを作成し、さびたラップトップで長さ、合計、最大値を計算するのに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ファイルから派生したボックス化されていないベクトルはメモリに収まるため、データの明らかなリレタリングが与えられた場合、これはすべて2倍高速で、動作がいくらか良くなります。 Vector.Uboxed http://hpaste.org/69270 もちろん、これは、タイプとフォールドの「乗算」がリビジョンなしでシーケンシャルタイプに一般化されるLogEntry ことに注意してください。またはsは、ByteString上で直接折りたたむことができます。さまざまなByteStringモジュールでsを使用するようにリレターして、最初にを定義する必要があります。しかし、のと製品FoldCharWord8foldBfoldfoldl'FoldFoldCharsは、 sまたはWord8sのリストまたはベクトルを折りたたむのと同じものです。

于 2012-05-30T04:47:47.340 に答える