skutecznie czyta duży plik na mapie

Question

Próbuję napisać kod, aby wykonać następujące proste zadanie w Haskell: wyszukiwanie etymologii słów przy użyciu tego słownika, przechowywanych jako duży plik tsv (http://www1.icsi.berkeley.edu/~demelo/etymwn/). Pomyślałem, że przeanalizuję (z attoparsec) plik tsv w Mapie, który mógłbym następnie użyć do efektywnego zbadania etymologii, w zależności od potrzeb (i innych rzeczy).

To był mój kod:

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

To działa dla małych ilości danych wejściowych, ale szybko rośnie zbyt nieefektywne. Nie jestem całkiem pewien, na czym polega problem i szybko zdałem sobie sprawę, że nawet trywialne zadania, takie jak przeglądanie ostatniej postaci pliku, trwały zbyt długo, gdy próbowałem, np. z

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

Moje pytania są następujące: jakie są główne rzeczy, które robię źle, pod względem podejścia i wykonania? Wszelkie wskazówki, jak uzyskać lepszy/lepszy kod?

Dzięki,

Reuben

Answer 1

Zauważ, że plik, który chcesz załadować ma 6 milionów linii i tekst jesteś zainteresowany przechowywania zawiera ok. 120 MB.

Dolna Bounds

Aby ustalić pewne granice dolne raz pierwszy stworzone inny plik .tsv zawierający z przetworzonych zawartość pliku etymwn.tsv. Następnie planowane jak zabrał się do tego programu perl czytać ten plik:

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

trwało to ok. 17 sekund, więc spodziewam się, że każdy program Haskell do zająć około tego czasu.

Jeśli czas rozruchu jest nie do zaakceptowania, należy rozważyć następujące opcje:

1. Praca w ghci i zastosować technikę „na żywo przeładunkowy”, aby zapisać mapę pomocą Foreign.Store package tak, że utrzymuje się przez ghci przeładowuje kod. W ten sposób wystarczy załadować dane mapy raz podczas iteracji kodu.
2. Użyj sklep klucz-wartość uporczywy (takie jak SQLite gdbm, BerkeleyDB)
3. dostęp do danych za pośrednictwem sklepu klient-serwer
4. Zmniejszyć liczbę par klucz-wartość, którą możliwy (zrobić trzeba wszystkie 6 ? milion)

Wariant 1 jest omówione w tym blogu przez Chrisa Gotowe:

• Reload Running Code in GHCI

Opcje 2 i 3 będą wymagały pracy w Monadzie IO.

Przetwarzanie

Przede wszystkim należy sprawdzić rodzaj swojej funkcji tsv:

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

wracasz listę map, a nie tylko jednej mapie. To nie wygląda dobrze.

Po drugie, jak zasugerował @chi, wątpię, czy używanie lnjest leniwy. W częściowej, musi sprawdzić, czy cała analiza się powiedzie, , więc nie widzę, jak nie można uniknąć tworzenia wszystkich przeanalizowanych linii przed powrotem.

Aby naprawdę analizować wejście leniwie, przyjąć następujące podejście:

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 

można nadal korzystać attoparsec wdrożyć toPair, ale można go używać na zasadzie linia po linii, zamiast na całym wejściu.

ByteString vs. Tekst

Z mojego doświadczenia w pracy z ByteStrings jest znacznie szybsze niż praca z tekstem.

Ta wersja toPair dla ByteStrings jest około 4 razy szybciej niż odpowiadająca wersji tekstu:

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

Albo, po prostu używać zwykłego funkcji 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" 

Większość czasu spędzonego ładowanie mapy polega na analizie linii. Dla ByteStrings jest to około 14 sekund. załadować wszystkie 6 milionów linii vs. 50 sekund. dla tekstu.

Answer 2

Aby dodać do this answer, chciałbym zauważyć, że attoparsec faktycznie ma bardzo dobre wsparcie dla "przyrostowego" analizowania przyrostowego. Możesz użyć tego bezpośrednio za pomocą wygodnej funkcji parseWith. Aby uzyskać jeszcze dokładniejszą kontrolę, można ręcznie podać parser za pomocą parse i feed. Jeśli nie chcesz się tym martwić, powinieneś móc użyć czegoś takiego jak pipes-attoparsec, ale osobiście uważam, że rury są nieco trudne do zrozumienia.