有效地将大文件读入Map

Question

我正在尝试编写代码以在Haskell中执行以下简单任务:使用此字典查找单词的词源,存储为大型tsv文件(http://www1.icsi.berkeley.edu/~demelo/etymwn/).我以为我会将tsv文件解析(使用attoparsec)到Map中,然后我可以根据需要使用它来高效地查找词源(并做一些其他的事情).

这是我的代码:

{-# LANGUAGE OverloadedStrings #-}

import Control.Arrow
import qualified Data.Map as M
import Control.Applicative
import qualified Data.Text as DT
import qualified Data.Text.Lazy.IO as DTLIO
import qualified Data.Text.Lazy as DTL
import qualified Data.Attoparsec.Text.Lazy as ATL
import Data.Monoid

text = do
    x <- DTLIO.readFile "../../../../etymwn.tsv"
    return $ DTL.take 10000 x

--parsers
wordpair = do
    x <- ATL.takeTill (== ':')
    ATL.char ':' *> (ATL.many' $ ATL.char ' ')
    y <- ATL.takeTill (\x -> x `elem` ['\t','\n'])
    ATL.char '\n' <|>   ATL.char '\t'
    return (x,y)

--line of file
line = do
    a <- (ATL.count 3 wordpair)
    case (rel (a !! 2)) of 
        True -> return . (\[a,b,c] -> [(a,c)]) $ a
        False -> return . (\[a,b,c] -> [(c,a)]) $ a
    where rel x = if x == ("rel","etymological_origin_of") then False else True

tsv = do 
    x <- ATL.many1 line
    return $ fmap M.fromList x

main = (putStrLn . show . ATL.parse tsv) =<< text

它适用于少量输入,但很快就会变得效率太低.我不太清楚问题出在哪里,并且很快就意识到,当我尝试时,即使查看文件的最后一个字符这样的琐碎任务也花了太长时间,例如

foo = fmap DTL.last $ DTLIO.readFile "../../../../etymwn.tsv

所以我的问题是:在方法和执行方面,我做错的主要事情是什么？有关更多Haskelly /更好代码的任何提示吗？

谢谢,

鲁本

Answer 1

请注意,您要加载的文件有600万行,您感兴趣的文本包含约.120 MB.

较低的界限

为了建立一些下界,我首先创建了另一个包含etymwn.tsv文件的预处理内容的.tsv文件.然后我计算了这个perl程序如何读取该文件:

my %H;
while (<>) {
  chomp;
  my ($a,$b) = split("\t", $_, 2);
  $H{$a} = $b;
}

这花费了大约.17秒,所以我希望任何Haskell程序能够占用大约时间.

如果此启动时间不可接受,请考虑以下选项:

1. 在ghci中工作并使用"实时重新加载"技术使用Foreign.Store包保存地图, 以便通过ghci代码重新加载来保持它.这样,您只需在迭代代码时加载一次地图数据.
2. 使用持久键值存储(例如sqlite,gdbm,BerkeleyDB)
3. 通过客户端 - 服务器存储访问数据
4. 减少存储的键值对的数量(你需要600万吗？)

Chris Done在这篇博客文章中讨论了选项1:

• 在GHCI中重新加载运行代码

选项2和3将要求您在IO monad中工作.

解析

首先,检查您的tsv功能类型:

tsv :: Data.Attoparsec.Internal.Types.Parser
          DT.Text [M.Map (DT.Text, DT.Text) (DT.Text, DT.Text)]

您将返回地图列表而不是仅返回一个地图.这看起来不对.

其次,正如@chi建议的那样,我怀疑使用attoparsec是懒惰的.在某种程度上,它必须验证整个解析是否成功,所以我无法看到它如何在返回之前无法避免创建所有已解析的行.

要真实地解析输入,请采用以下方法:

toPair :: DT.Text -> (Key, Value)
toPair input = ...

main = do
  all_lines <- fmap DTL.lines $ DTLIO.getContent
  let m = M.fromList $ map toPair all_lines
  print $ M.lookup "foobar" m

您仍然可以使用它attoparsec来实现toPair,但是您将逐行使用它而不是整个输入.

ByteString与文本

根据我的经验,使用ByteStrings比使用Text快得多.

此版本的toPairByteStrings比Text的相应版本快4倍:

{-# LANGUAGE OverloadedStrings #-}
import qualified Data.ByteString.Lazy.Char8 as L
import qualified Data.Attoparsec.ByteString.Char8 as A
import qualified Data.Attoparsec.ByteString.Lazy as AL

toPair :: L.ByteString -> (L.ByteString, L.ByteString)
toPair bs =
  case AL.maybeResult (AL.parse parseLine bs) of
    Nothing    -> error "bad line"
    Just (a,b) -> (a,b)
  where parseLine = do
          A.skipWhile (/= ' ')
          A.skipWhile (== ' ')
          a <- A.takeWhile (/= '\t')
          A.skipWhile (== '\t')
          rel <- A.takeWhile (/= '\t')
          A.skipWhile (== '\t')
          A.skipWhile (/= ' ')
          A.skipWhile (== ' ')
          c <- A.takeWhile (const True)
          if rel == "rel:etymological_origin_of"
            then return (c,a)
            else return (a,c)

或者,只使用普通的ByteString函数:

fields :: L.ByteString -> [L.ByteString]
fields = L.splitWith (== '\t')

snipSpace = L.ByteString -> L.ByteString
snipSpace = L.dropWhile (== ' ') . L.dropWhile (/=' ')

toPair'' bs = 
  let fs = fields bs
  case fields line of
    (x:y:z:_) -> let a = snipSpace x
                     c = snipSpace z
                 in
                 if y == "rel:etymological_origin_of"
                   then (c,a)
                   else (a,c)
    _         -> error "bad line"

加载地图所花费的大部分时间都是解析线条.对于ByteStrings,这大约是14秒.加载所有600万行而不是50秒.对于文本.