эффективно читает большой файл на карте

Question

Я пытаюсь написать код для выполнения следующей простой задачи в Haskell: поиск этимологий слов с использованием этого словаря, хранящихся в виде большого файла TSV (http://www1.icsi.berkeley.edu/~demelo/etymwn/). Я думал, что я проанализирую (с attoparsec) файл tsv на Карте, который я мог бы использовать для эффективного поиска этимологий, как требуется (и делать некоторые другие вещи).

Это был мой код:

{-# 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

Обратите внимание, что файл, который вы хотите загрузить имеет 6 миллионов строк и текст, который вы заинтересованы в хранении включает ок. 120 МБ.

Нижние границы

Чтобы установить нижние оценки я первый создал еще один файл, содержащий .tsv препроцессированный содержимое файла etymwn.tsv. Я тогда приурочен, как это потребовалось для этого перл программы для чтения файла:

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

Это произошло ки. 17 сек., Поэтому я ожидаю, что любая программа Haskell до займет примерно столько же времени.

Если время запуска неприемлем, рассмотрим следующие варианты:

1. Работа в GHCI и использовать технику «живой перегрузочной», чтобы сохранить карту используя Foreign.Store package так, что она сохраняется через GHCI перезагрузка кода. Таким образом, вы должны загружать только данные карты один раз, когда вы повторяете свой код.
2. Используйте постоянное хранилище ключа-значения (например, SQLite, GDBM, BerkeleyDB)
3. Доступа к данным через магазин клиент-сервер
4. Снизить количество пара ключа-значения, вы хранить (вам нужно все- ? млн)

Вариант 1 обсуждается в этом блоге Крис Done:

• Reload Running Code in 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 является ленивым. В partcular он должен проверить, что весь синтаксический анализ завершен, , поэтому я не вижу, как он не может избежать создания всех проанализированных строк перед возвратом.

Чтобы разобрать поистине вход лениво, принять следующий подход:

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, но вы будете использовать его на основе линии по линии вместо на весь вход.

байтовой строки против Текст

По моему опыту работы с байтовых строк гораздо быстрее, чем работа с текстом.

Эта версия toPair для байтовых строк примерно в 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) 

Или просто использовать простые байтовой строки функции:

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 сек. загрузить все 6 миллионов строк против 50 секунд. для текста.

Answer 2

Чтобы добавить к this answer, я хотел бы отметить, что attoparsec фактически имеет очень хорошую поддержку инкрементного синтаксического анализа «pull-based». Вы можете использовать это непосредственно с помощью удобной функции parseWith. Для более тонкого управления вы можете подавать парсер вручную с помощью parse и feed. Если вы не хотите беспокоиться об этом, вы должны использовать что-то вроде pipes-attoparsec, но лично я нахожу трубы немного трудными для понимания.