有效地将大文件读入地图

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/better 代码的任何提示？

谢谢，

鲁本

Answer 1

请注意，您要加载的文件有 600 万行并且您有兴趣存储的文本包含大约。 120 MB。

下界

为了建立一些下限，我首先创建了另一个 .tsv 文件，其中包含 etymwn.tsv 文件的预处理内容。然后我计时如何让这个 perl 程序读取那个文件：

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

这花了大约。 17 秒，所以我希望任何 Haskell 程序花那么多时间。

如果这个启动时间不可接受，请考虑以下选项：

在 ghci 中工作并使用 "live reloading" 技术保存地图使用 Foreign.Store package 以便它通过 ghci 代码重新加载持续存在。这样，您只需在迭代代码时加载一次地图数据。
使用持久键值存储（例如 sqlite、gdbm、BerkeleyDB）
通过客户端-服务器存储访问数据
减少存储的键值对数量（需要全部 600 万吗？）

Chris Done 在这篇博客 post 中讨论了选项 1：

Reload Running Code in 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，但您将使用它逐行而不是整个输入。

字节串与文本

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

此版本的 toPair for 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"

加载地图的大部分时间都花在解析线条上。对于 ByteStrings，这大约是 14 秒。加载所有 600 万行对比 50 秒。对于文本。

Answer 2

补充，我想指出 attoparsec 实际上对 "pull-based" 增量解析有很好的支持。您可以通过方便的 parseWith 函数直接使用它。为了更好地控制，您可以用 parse 和 feed 手动输入解析器。如果你不想担心这些，你应该可以使用像 pipes-attoparsec 这样的东西，但我个人觉得管道有点难以理解。

有效地将大文件读入地图

efficiently reading a large file into a Map

io

performance

haskell

hashmap

attoparsec

下界

正在解析

字节串与文本