5

Haskellを使用して、ファイル内の文字の頻度を見つけようとしています。〜500MBのサイズのファイルを処理できるようにしたい。

今まで試したこと

  1. それは仕事をしますが、ファイルを256回解析するので少し遅いです

    calculateFrequency :: L.ByteString -> [(Word8, Int64)]
calculateFrequency f = foldl (\acc x -> (x, L.count x f):acc) [] [255, 254.. 0]

  2. Data.Map も使用してみましたが、プログラムがメモリ不足になります (ghc インタープリターで)。

    import qualified Data.ByteString.Lazy as L
import qualified Data.Map as M

calculateFrequency' :: L.ByteString -> [(Word8, Int64)]
calculateFrequency' xs = M.toList $ L.foldl' (\m word -> M.insertWith (+) word 1 m) (M.empty) xs
4

4 に答える 4

14

これは、より高いレベルの構造の代わりに、変更可能なボックス化されていないベクトルを使用した実装です。conduitまた、遅延 I/O を回避するためにファイルの読み取りにも使用します。

import           Control.Monad.IO.Class
import qualified Data.ByteString             as S
import           Data.Conduit
import           Data.Conduit.Binary         as CB
import qualified Data.Conduit.List           as CL
import qualified Data.Vector.Unboxed.Mutable as VM
import           Data.Word                   (Word8)

type Freq = VM.IOVector Int

newFreq :: MonadIO m => m Freq
newFreq = liftIO $ VM.replicate 256 0

printFreq :: MonadIO m => Freq -> m ()
printFreq freq =
    liftIO $ mapM_ go [0..255]
  where
    go i = do
        x <- VM.read freq i
        putStrLn $ show i ++ ": " ++ show x

addFreqWord8 :: MonadIO m => Freq -> Word8 -> m ()
addFreqWord8 f w = liftIO $ do
    let index = fromIntegral w
    oldCount <- VM.read f index
    VM.write f index (oldCount + 1)

addFreqBS :: MonadIO m => Freq -> S.ByteString -> m ()
addFreqBS f bs =
    loop (S.length bs - 1)
  where
    loop (-1) = return ()
    loop i = do
        addFreqWord8 f (S.index bs i)
        loop (i - 1)

-- | The main entry point.
main :: IO ()
main = do
    freq <- newFreq
    runResourceT
        $  sourceFile "random"
        $$ CL.mapM_ (addFreqBS freq)
    printFreq freq

これを 500MB のランダム データで実行し、@josejuan の UArray ベースの回答と比較しました。

  • コンジットベース/可変ベクトル: 1.006s
  • Uアレイ: 17.962秒

josejuan のハイレベルなアプローチの優雅さの多くを維持しながら、可変ベクトル実装の速度を維持することは可能だと思いますが、そのようなものを実装する機会はまだありません。また、一部の汎用ヘルパー関数 (Data.ByteString.mapM や Data.Conduit.Binary.mapM など) を使用すると、パフォーマンスに影響を与えずに実装を大幅に簡素化できることに注意してください。

FP Haskell Center でもこの実装を試すことができます。

編集:不足している機能の1つを追加conduitし、コードを少しクリーンアップしました。次のようになります。

import           Control.Monad.Trans.Class   (lift)
import           Data.ByteString             (ByteString)
import           Data.Conduit                (Consumer, ($$))
import qualified Data.Conduit.Binary         as CB
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           System.IO                   (stdin)

freqSink :: Consumer ByteString IO (V.Vector Int)
freqSink = do
    freq <- lift $ VM.replicate 256 0
    CB.mapM_ $ \w -> do
        let index = fromIntegral w
        oldCount <- VM.read freq index
        VM.write freq index (oldCount + 1)
    lift $ V.freeze freq

main :: IO ()
main = (CB.sourceHandle stdin $$ freqSink) >>= print

機能上の唯一の違いは、周波数がどのように出力されるかです。

于 2014-01-15T10:24:43.087 に答える
4

これは私のコンピューターで機能します：

module Main where
import qualified Data.HashMap.Strict as M
import qualified Data.ByteString.Lazy as L
import Data.Word
import Data.Int

calculateFrequency :: L.ByteString -> [(Word8, Int64)]
calculateFrequency xs = M.toList $ L.foldl' (\m word -> M.insertWith (+) word 1 m) M.empty xs

main = do
    bs <- L.readFile "E:\\Steam\\SteamApps\\common\\Sid Meier's Civilization V\\Assets\\DLC\\DLC_Deluxe\\Behind the Scenes\\Behind the Scenes.wmv"
    print (calculateFrequency bs)

メモリが不足したり、ファイル全体をロードしたりすることはありませんが、600 MB 以上のファイルでは永遠に (約 1 分) かかります! 私はghc 7.6.3を使ってこれをコンパイルしました。

HashMaplazy の代わりにstrict を除いて、コードは基本的に同一であることを指摘しておく必要がありますMap。

は、この場合よりもinsertWith2 倍高速であることに注意してください。私のマシンでは、書かれたコードは 54 秒で実行されますが、使用しているバージョンは 107 秒かかります。HashMapMapMap

于 2014-01-15T08:36:11.067 に答える
0

私の 2 セント (STUArray を使用)。ここで他のソリューションと比較することはできません。試してみたい人もいるかも…

module Main where

import Data.Array.ST (runSTUArray, newArray, readArray, writeArray)
import Data.Array.Unboxed (UArray)
import qualified Data.ByteString.Lazy as L (ByteString, unpack, getContents)
import Data.Word
import Data.Int
import Control.Monad (forM_)

calculateFrequency :: L.ByteString -> UArray Word8 Int64 
calculateFrequency bs = runSTUArray $ do
    a <- newArray (0, 255) 0
    forM_ (L.unpack bs) $ \i -> readArray a i >>= writeArray a i . succ
    return a

main = L.getContents >>= print . calculateFrequency
于 2014-01-15T19:08:26.320 に答える