Costruire un istogramma con haskell, molte volte più lento che con python

Question

Stavo andando a testare la classificazione bayes naive. Una parte di questo stava per costruire un istogramma dei dati di allenamento. Il problema è che sto usando una grande quantità di dati di addestramento, la mailing list haskell-cafe da un paio di anni fa, e ci sono oltre 20k file nella cartella.

Ci vuole un po 'più di due minuti per creare l'istogramma con python e poco più di 8 minuti con haskell. Sto usando Data.Map (insertWith '), enumeratori e testo. Cos'altro posso fare per accelerare il programma?

Haskell:

import qualified Data.Text as T 
import qualified Data.Text.IO as TI 
import System.Directory 
import Control.Applicative 
import Control.Monad (filterM, foldM) 
import System.FilePath.Posix ((</>)) 
import qualified Data.Map as M 
import Data.Map (Map) 
import Data.List (foldl') 
import Control.Exception.Base (bracket) 
import System.IO (Handle, openFile, hClose, hSetEncoding, IOMode(ReadMode), latin1) 
import qualified Data.Enumerator as E 
import Data.Enumerator (($$), (>==>), (<==<), (==<<), (>>==), ($=), (=$)) 
import qualified Data.Enumerator.List as EL 
import qualified Data.Enumerator.Text as ET 



withFile' :: (Handle -> IO c) -> FilePath -> IO c 
withFile' f fp = do 
    bracket 
    (do 
     h ← openFile fp ReadMode 
     hSetEncoding h latin1 
     return h) 
    hClose 
    (f) 

buildClassHistogram c = do 
    files ← filterM doesFileExist =<< map (c </>) <$> getDirectoryContents c 
    foldM fileHistogram M.empty files 

fileHistogram m file = withFile' (λh → E.run_ $ enumHist h) file 
    where 
    enumHist h = ET.enumHandle h $$ EL.fold (λm' l → foldl' (λm'' w → M.insertWith' (const (+1)) w 1 m'') m' $ T.words l) m 

Python:

for filename in listdir(root): 
    filepath = root + "/" + filename 
    # print(filepath) 
    fp = open(filepath, "r", encoding="latin-1") 
    for word in fp.read().split(): 
     if word in histogram: 
      histogram[word] = histogram[word]+1 
     else: 
      histogram[word] = 1 

Edit: importazioni aggiunti

Answer 1

Si potrebbe provare a utilizzare le mappe hash imperative dal pacchetto hashtables: http://hackage.haskell.org/package/hashtables Ricordo che una volta ho ottenuto un moderato aumento rispetto a Data.Map. Non mi aspetterei comunque nulla di spettacolare.

UPDATE

ho semplificato il codice python così ho potuto testarlo su un singolo file di grandi dimensioni (100 milioni di linee):

import sys 
histogram={} 
for word in sys.stdin.readlines(): 
    if word in histogram: 
     histogram[word] = histogram[word]+1 
    else: 
     histogram[word] = 1 
print histogram.get("the") 

prende 6,06 secondi

traduzione Haskell utilizzando hashtables :

{-# LANGUAGE OverloadedStrings #-} 
import qualified Data.ByteString.Char8 as T 
import qualified Data.HashTable.IO as HT 
main = do 
    ls <- T.lines `fmap` T.getContents 
    h <- HT.new :: IO (HT.BasicHashTable T.ByteString Int) 
    flip mapM_ ls $ \w -> do 
    r <- HT.lookup h w 
    case r of 
     Nothing -> HT.insert h w (1::Int) 
     Just c -> HT.insert h w (c+1) 
    HT.lookup h "the" >>= print 

Esegui con una grande area di allocazione: histogram +RTS -A500M Prende 9,3 secondi, con 2,4% di GC. Ancora un po 'più lento di Python ma non troppo male.

Secondo il GHC user guide, è possibile modificare le RTS opzioni durante la compilazione:

GHC lets you change the default RTS options for a program at compile time, using the -with-rtsopts flag (Section 4.12.6, “Options affecting linking”). A common use for this is to give your program a default heap and/or stack size that is greater than the default. For example, to set -H128m -K64m, link with -with-rtsopts="-H128m -K64m".

Answer 2

vostri Haskell e Python implementazioni utilizzano mappe con diverse complessità. I dizionari Python sono mappe hash quindi il tempo previsto per ciascuna operazione (test di appartenenza, ricerca e inserimento) è O (1). La versione di Haskell utilizza Data.Map che è un albero di ricerca binario bilanciato in modo che le stesse operazioni richiedano il tempo O (lg n). Se cambi la tua versione di Haskell per usare un'implementazione di mappa diversa, ad esempio una tabella hash o una specie di trie, dovrebbe essere molto più veloce. Tuttavia, non ho familiarità con i diversi moduli che implementano queste strutture dati per dire quale sia il migliore. Vorrei iniziare con the Data category on Hackage e cercare quello che ti piace. Potresti anche cercare una mappa che consenta aggiornamenti distruttivi come STArray.

Answer 3

Abbiamo bisogno di maggiori informazioni:

• Quanto tempo ci vuole entrambi i programmi per elaborare le parole del input, senza struttura dati per il mantenimento dei conteggi?

• Quante parole distinte ci sono, quindi possiamo giudicare se il costo extra log N per alberi bilanciati è una considerazione?

• Che cosa dice il profilo di GHC? In particolare, quanto tempo è dedicato all'assegnazione? È possibile che la versione di Haskell passi la maggior parte del tempo a allocare nodi ad albero che diventano rapidamente obsoleti.

• UPDATE: Mi sono perso quel "testo" minuscolo potrebbe significare Data.Text. È possibile che si stiano confrontando applica e arance. La codifica Latin1 di Python utilizza un byte per carattere. Sebbene tenti di essere efficiente, Data.Text deve consentire la possibilità di più di 256 caratteri. Cosa succede se passi a String, o meglio, Data.ByteString?

A seconda di ciò che dicono questi indicatori, qui un paio di cose da provare:

• Se analizzando l'ingresso è un collo di bottiglia, provare a guidare tutto il vostro I/O e di analisi da Data.ByteString invece di Text.

• Se la struttura dei dati è un collo di bottiglia, Bentley e Sedgewick ternary search trees sono puramente funzionali ma eseguono in modo concorrenziale con tabelle hash. C'è un pacchetto TernaryTrees su Hackage.