3

既存のMapReduce実装（ Real World Haskellの実装）を使用して簡単なプログラムを作成しようとしています。

フレームワークの使用例として、ファイル内の単語数をカウントするコードを次に示します。

module Main where

import Control.Monad (forM_)
import Data.Int (Int64)
import qualified Data.ByteString.Lazy.Char8 as LB
import System.Environment (getArgs)

import LineChunks (chunkedReadWith)
import MapReduce (mapReduce, rdeepseq)

wordCount :: [LB.ByteString] -> Int
wordCount = mapReduce rdeepseq (length . LB.words)
                      rdeepseq sum

main :: IO ()
main = do
  args <- getArgs
  forM_ args $ \path -> do
    numWords <- chunkedReadWith wordCount path
    putStrLn $ "Words: " ++ show numWords

同じMapReduceフレームワークを使用して、文字列（ "il"など）を検索し、見つかった行番号を返すプログラムを作成する必要があります。たとえば、出力は次のようになります。

verILy: found on lines 34, 67, 23
ILlinois: found on lines 1, 2, 56
vILla: found on lines 4, 5, 6

（「il」の大文字化は必要ありません。）

私はHaskellの初心者で、具体的なアイデアはまだありません。Data.ByteString.Lazy.Char8クラスにメンバー関数があることに気づきましたfindIndices。これを使用することは可能ですか？

正しい方向へのコードやヒントをいただければ幸いです。

4

1 に答える 1

3

よし、これを打ってみよう。

まず、文字列内の単語を見つける方法が必要です。regex-tdfaそれは正規表現を使用して行うことができます。パッケージとしましょう。Haskell 正規表現パッケージは優れていますが、非常に一般的で、最初は少し読みにくいものです。(=~)ほとんどの場合、型を具体的にするために、一致する演算子の単なるラッパーである関数を作成します。

wordHere :: LB.ByteString -> LB.ByteString -> Bool
wordHere word string = string =~ word
-- a.k.a.            = flip (=~)

ここで、タイプの多くの並列ローカル「マッピング」ジョブをさまざまなスパークに与えてから、 mapReducereduceジョブのすべての結果を. 通常、reduce ステップの順序の保証はありませんが、RWH では実際にその保証が得られます。([a] -> c)(a -> b)([b] -> c)mapReduce

実際、 RWH のlineChunks関数は、ドキュメント (LB.ByteString -> [LB.ByteString]) を少数の行のチャンクに分割します。マッピング ジョブはそれぞれ、これらのチャンクの 1 つを取得し、行の一致に関する情報をローカルに提供する必要があります。これを行うには、チャンクを構成行に分割し、行にローカルに番号を付け、それらをマッピングし、 true が返さwordHereれたローカル行番号を収集します。wordHere通常は最初に実行しwordHere、任意の述語に置き換えますp :: (LB.ByteString -> Bool)

import Control.Arrow

localLinesTrue :: (LB.ByteString -> Bool) -> [LB.ByteString] -> [Int]
localLinesTrue p ls = map fst . filter snd . map (second p) . zip [1..]

これで、 のようなローカル マッパーを作成できますlocalLinesTrue (wordHere $ LB.pack "foobar") . LB.lines :: LB.ByteString -> [Int]。

そのタイプの特定のマッパーは、残りの関数のタイプも少し説明します。私たちは今持っています

>>> :t mapReduce rdeepseq (localLinesTrue (wordHere "foo")) rdeepseq
...    :: ([[Int]] -> c) -> [LB.ByteString] -> c

したがって、レデューサーは type でなければなりません([[Int]] -> c)。よし、作ってみよう。s のリストのリストがある場合Int、実際の行番号を再構築できます...

[[], [], [], [5], [3], [], []]

待ってください、実際にはできません。各チャンクで発生する行数など、マッパーにさらに情報を追加する必要があります。幸いなことに、私たちは慎重に絡み合っていないものを維持しているので、これは簡単に追加できます. ([Int], Int)2 番目のパラメーターがそのチャンクの行数であるような戻り値の型が必要です。"fanout" でそれを行うことができます(&&&)。

mapper regex = (localLinesTrue (wordHere regex) &&& length) . LB.lines

出力は次のようになります

[ ([], 3),  ([], 5),  ([3, 5], 10), ... ]

Stateモナドを使用してカウントするだけのレデューサーを実装できます

reducerStep :: ([Int], Int) -> State Int [Int]
reducerStep (hits, count) = do pos <- get
                               modify (+count)
                               return (map (+pos) hits)

reducer :: [([Int], Int)] -> [Int]
reducer = concat . evalState 0 . mapM reducerStep

そして、私たちは持っています

mapReduce rdeepseq (mapper regex)
          rdeepseq reducer
  :: [LB.ByteString] -> [Int]

これで、最後まで 95% を達成できるはずです。

于 2013-03-06T18:54:09.787 に答える