lettura efficiente di un file di grandi dimensioni in una mappa

Question

Sto cercando di scrivere codice per eseguire il seguente semplice compito in Haskell: cercare le etimologie delle parole usando questo dizionario, memorizzato come un file tsv di grandi dimensioni (http://www1.icsi.berkeley.edu/~demelo/etymwn/). Ho pensato di analizzare (con attoparsec) il file tsv in una mappa, che potrei quindi utilizzare per cercare in modo efficiente l'etimologia, come richiesto (e fare altre cose con).

Questo è stato il mio codice:

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

Si lavora per piccole quantità di ingresso, ma rapidamente cresce troppo inefficiente. Non sono del tutto chiaro su quale sia il problema, e presto mi sono reso conto che anche compiti banali come la visualizzazione dell'ultimo carattere del file richiedevano troppo tempo quando ho provato, ad es. con

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

Quindi le mie domande sono: quali sono le cose principali che sto sbagliando, in termini di approccio ed esecuzione? Qualche consiglio per più codice Haskelly/migliore?

Grazie,

Reuben

Answer 1

Si noti che il file che si desidera caricare dispone di 6 milioni di linee e il testo che ti interessa memorizzazione comprende circa. 120 MB.

Lower Bounds

di stabilire alcuni limiti inferiori in primo luogo ho creato un altro file di .tsv contenente il contenuto del file preprocessati etymwn.tsv. Poi ho cronometrato come ha preso per questo programma Perl per leggere quel file:

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

Questo ha avuto circa. 17 secondi, quindi mi aspetterei che un qualsiasi programma Haskell su occupasse circa il tempo.

Se questo tempo di avvio è inaccettabile, considerare le seguenti opzioni:

1. Lavori in ghci e utilizzare la tecnica del "ricarico dal vivo" per salvare la mappa utilizzando il Foreign.Store package in modo che persiste attraverso ghci ricarica del codice. In questo modo è sufficiente caricare i dati della mappa una volta mentre si itera il codice.
2. utilizzare un archivio di valori-chiave persistenti (come ad esempio SQLite, gdbm, BerkeleyDB)
3. accedere ai dati attraverso un negozio client-server
4. ridurre il numero di coppie chiave-valore di memorizzare (Avete bisogno di tutti e 6 ? milioni)

Opzione 1 è discusso in questo post del blog da Chris Fatto:

• Reload Running Code in GHCI

Le opzioni 2 e 3 richiedono di lavorare nella monade IO.

Analisi

Prima di tutto, controllare il tipo di funzione tsv:

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

si restituisce un elenco di mappe invece di uno solo carta. Questo non ha l'aspetto giusto.

In secondo luogo, come suggerito da @chi, dubito che l'uso di attoparsec sia pigro. In partcolare, deve verificare che l'intera analisi abbia esito positivo, , quindi non riesco a vedere come non possa evitare di creare tutte le righe analizzate prima di tornare.

per analizzare veramente l'ingresso pigramente, seguirà il seguente approccio:

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 

È comunque possibile utilizzare per implementare attoparsectoPair, ma che verrà usato è con il metodo integrale al posto di sull'intero input.

ByteString vs. Testo

Nella mia esperienza di lavoro con stringhe di byte è molto più veloce rispetto a lavorare con il testo.

Questa versione di toPair per stringhe di byte è circa 4 volte più veloce rispetto alla corrispondente versione per testo:

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

Oppure, basta usare semplici funzioni 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" 

La maggior parte del tempo trascorso caricamento della mappa è in analisi delle linee. Per ByteStrings questo è di circa 14 sec. caricare tutti i 6 milioni di linee contro 50 secondi. per il testo.

Answer 2

Per aggiungere a this answer, mi piacerebbe notare che in realtà l'attoparsec ha un ottimo supporto per l'analisi incrementale "pull-based". È possibile utilizzarlo direttamente con la comoda funzione parseWith. Per un controllo ancora più preciso, è possibile alimentare il parser a mano con parse e feed. Se non vuoi preoccuparti di questo, dovresti essere in grado di usare qualcosa come pipes-attoparsec, ma personalmente trovo le pipe un po 'difficili da capire.