有效地将大文件读取到Map中

Question

我试图在Haskell中编写执行以下简单任务的代码:使用此字典查找单词的词源，该字典存储为大型tsv文件(http://www1.icsi.berkeley.edu/~demelo/etymwn/)。我认为我应该(使用attoparsec)将tsv文件解析为一个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。

<标题>下界h1> 了建立一些下限，我首先创建了另一个.tsv文件，其中包含词源的预处理内容。tsv文件。然后我计时了一下这个perl程序读取这个文件:

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

这花了大约。17秒。，所以我希望任何Haskell程序都能

如果无法接受此启动时间，请考虑以下选项:

1. 在ghci中工作，并使用"实时重新加载"技术保存地图使用外文。存储方案这样它就可以通过重新加载ghci代码而持续存在。这样你只需要在迭代代码时加载一次地图数据。
2. 使用持久键值存储(如sqlite, gdbm, BerkeleyDB)
3. 通过客户机-服务器存储访问数据
4. 减少您存储的键值对的数量(您需要全部600万吗?)

选项1由Chris Done在这篇博文中讨论:

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

选项2和3将要求您在IO单子中工作。

<标题>解析

首先，检查您的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与Text

根据我的经验，使用bytestring要比使用Text快得多。

这个版本的toPair的ByteStrings比对应的快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"

加载映射的大部分时间花在解析行上。对于bytestring，加载所有600万行大约需要14秒对比50秒。对文本。

Answer 2

为了补充这个答案，我想指出，attoparsec实际上非常支持"基于拉的"增量解析。您可以通过方便的parseWith函数直接使用它。为了获得更精细的控制，您可以手动向解析器提供parse和feed。如果你不想担心这些，你应该能够使用像pipes-attoparsec这样的东西，但我个人觉得管道有点难以理解。