我正在尝试使用查找文件中字符的频率Haskell。我希望能够处理大约 500MB 大小的文件。
到目前为止我已经尝试过的
-
它完成了这项工作,但有点慢,因为它解析了文件 256 次
calculateFrequency :: L.ByteString -> [(Word8, Int64)]
calculateFrequency f = foldl (\acc x -> (x, L.count x f):acc) [] [255, 254.. 0]
-
我也尝试过使用 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
这是使用可变的、未装箱的向量而不是更高级别的构造的实现。它还使用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
- UArray:17.962s
我认为应该可以保留 josejuan 的高级方法的大部分优雅性,同时保持可变向量实现的速度,但我还没有机会尝试实现类似的东西。另请注意,使用一些通用辅助函数(如 Data.ByteString.mapM 或 Data.Conduit.Binary.mapM),实现可能会更加简单,而不会影响性能。
You can 在 FP Haskell Center 上尝试这个实现 https://www.fpcomplete.com/user/snoyberg/random-code-snippets/conduit-frequency-of-characters以及。
EDIT:我添加了其中一个缺失的功能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
功能上的唯一区别是频率的打印方式。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)