Ottimizzazione del codice Haskell

Question

Sto cercando di imparare Haskell e dopo un articolo su reddit sulle catene di testo Markov, ho deciso di implementare la generazione del testo Markov prima in Python e ora in Haskell. Tuttavia ho notato che la mia implementazione in Python è molto più veloce della versione di Haskell, persino Haskell è compilato in codice nativo. Mi chiedo cosa dovrei fare per far funzionare il codice Haskell più velocemente e per ora credo sia molto più lento a causa dell'utilizzo di Data.Map invece di hashmaps, ma non sono sicuro

Inserirò il codice Python e anche Haskell. Con gli stessi dati, Python impiega circa 3 secondi e Haskell è più vicino a 16 secondi.

È ovvio che prenderò qualche critica costruttiva :).

import random 
import re 
import cPickle 
class Markov: 
    def __init__(self, filenames): 
     self.filenames = filenames 
     self.cache = self.train(self.readfiles()) 
     picklefd = open("dump", "w") 
     cPickle.dump(self.cache, picklefd) 
     picklefd.close() 

    def train(self, text): 
     splitted = re.findall(r"(\w+|[.!?',])", text) 
     print "Total of %d splitted words" % (len(splitted)) 
     cache = {} 
     for i in xrange(len(splitted)-2): 
      pair = (splitted[i], splitted[i+1]) 
      followup = splitted[i+2] 
      if pair in cache: 
       if followup not in cache[pair]: 
        cache[pair][followup] = 1 
       else: 
        cache[pair][followup] += 1 
      else: 
       cache[pair] = {followup: 1} 
     return cache 

    def readfiles(self): 
     data = "" 
     for filename in self.filenames: 
      fd = open(filename) 
      data += fd.read() 
      fd.close() 
     return data 

    def concat(self, words): 
     sentence = "" 
     for word in words: 
      if word in "'\",?!:;.": 
       sentence = sentence[0:-1] + word + " " 
      else: 
       sentence += word + " " 
     return sentence 

    def pickword(self, words): 
     temp = [(k, words[k]) for k in words] 
     results = [] 
     for (word, n) in temp: 
      results.append(word) 
      if n > 1: 
       for i in xrange(n-1): 
        results.append(word) 
     return random.choice(results) 

    def gentext(self, words): 
     allwords = [k for k in self.cache] 
     (first, second) = random.choice(filter(lambda (a,b): a.istitle(), [k for k in self.cache])) 
     sentence = [first, second] 
     while len(sentence) < words or sentence[-1] is not ".": 
      current = (sentence[-2], sentence[-1]) 
      if current in self.cache: 
       followup = self.pickword(self.cache[current]) 
       sentence.append(followup) 
      else: 
       print "Wasn't able to. Breaking" 
       break 
     print self.concat(sentence) 

Markov(["76.txt"]) 

-

module Markov 
(train 
, fox 
) where 

import Debug.Trace 
import qualified Data.Map as M 
import qualified System.Random as R 
import qualified Data.ByteString.Char8 as B 


type Database = M.Map (B.ByteString, B.ByteString) (M.Map B.ByteString Int) 

train :: [B.ByteString] -> Database 
train (x:y:[]) = M.empty 
train (x:y:z:xs) = 
    let l = train (y:z:xs) 
    in M.insertWith' (\new old -> M.insertWith' (+) z 1 old) (x, y) (M.singleton z 1) `seq` l 

main = do 
    contents <- B.readFile "76.txt" 
    print $ train $ B.words contents 

fox="The quick brown fox jumps over the brown fox who is slow jumps over the brown fox who is dead." 

Answer 1

Ho cercato di evitare di fare qualcosa di sofisticato o sottile. Questi sono solo due approcci per fare il raggruppamento; il primo enfatizza la corrispondenza del modello, il secondo no.

import Data.List (foldl') 
import qualified Data.Map as M 
import qualified Data.ByteString.Char8 as B 

type Database2 = M.Map (B.ByteString, B.ByteString) (M.Map B.ByteString Int) 

train2 :: [B.ByteString] -> Database2 
train2 words = go words M.empty 
    where go (x:y:[]) m = m 
      go (x:y:z:xs) m = let addWord Nothing = Just $ M.singleton z 1 
           addWord (Just m') = Just $ M.alter inc z m' 
           inc Nothing = Just 1 
           inc (Just cnt) = Just $ cnt + 1 
          in go (y:z:xs) $ M.alter addWord (x,y) m 

train3 :: [B.ByteString] -> Database2 
train3 words = foldl' update M.empty (zip3 words (drop 1 words) (drop 2 words)) 
    where update m (x,y,z) = M.alter (addWord z) (x,y) m 
      addWord word = Just . maybe (M.singleton word 1) (M.alter inc word) 
      inc = Just . maybe 1 (+1) 

main = do contents <- B.readFile "76.txt" 
      let db = train3 $ B.words contents 
      print $ "Built a DB of " ++ show (M.size db) ++ " words" 

penso che siano entrambi più veloce rispetto alla versione originale, ma certamente li ho provati solo contro il primo corpus ragionevole che ho trovato.

EDIT Secondo punto molto valido di Travis Brown,

train4 :: [B.ByteString] -> Database2 
train4 words = foldl' update M.empty (zip3 words (drop 1 words) (drop 2 words)) 
    where update m (x,y,z) = M.insertWith (inc z) (x,y) (M.singleton z 1) m 
      inc k _ = M.insertWith (+) k 1 

Answer 2

a) Come ti compilarlo? (ghc -O2?)

b) Quale versione di GHC?

c) Data.Map è piuttosto efficiente, ma puoi essere ingannato in aggiornamenti pigri - usa insertWith ', non insertWithKey.

d) Non convertire i simboli in stringa. Mantenerli come segni di estrapolazione e memorizzarli nella Mappa

Answer 3

Come suggerito da Don, cerca di utilizzare le versioni più severe delle tue funzioni: insertWithKey '(e M.insertWith' poiché ignori il parametro chiave la seconda volta).

Sembra che il tuo codice generi probabilmente un sacco di thunk fino alla fine del tuo [String].

Partenza: http://book.realworldhaskell.org/read/profiling-and-optimization.html

... soprattutto provare graficamente la heap (circa a metà del capitolo). Interessato a vedere cosa trovi.

Answer 4

1) Non sono chiaro sul codice. a) Si definisce "volpe" ma non lo si usa. Intendevi per noi cercare di aiutarti a usare "volpe" invece di leggere il file? b) Si dichiara come "modulo Markov", quindi si ha un 'main' nel modulo. c) System.Random non è necessario. Ci aiuta ad aiutarti se pulisci un po 'il codice prima di postare.

2) Utilizzare ByteStrings e alcune operazioni rigide come ha detto Don.

3) Compilare con -O2 e utilizzare -fforce-recomp per accertarsi di aver ricompilato il codice.

4) Prova questa leggera trasformazione, funziona molto velocemente (0,005 secondi). Ovviamente l'input è assurdamente piccolo, quindi è necessario fornire il file o semplicemente testarlo da soli.

{-# LANGUAGE OverloadedStrings, BangPatterns #-} 
module Main where 

import qualified Data.Map as M 
import qualified Data.ByteString.Lazy.Char8 as B 


type Database = M.Map (B.ByteString, B.ByteString) (M.Map B.ByteString Int) 

train :: [B.ByteString] -> Database 
train xs = go xs M.empty 
    where 
    go :: [B.ByteString] -> Database -> Database 
    go (x:y:[]) !m = m 
    go (x:y:z:xs) !m = 
    let m' = M.insertWithKey' (\key new old -> M.insertWithKey' (\_ n o -> n + 1) z 1 old) (x, y) (M.singleton z 1) m 
    in go (y:z:xs) m' 

main = print $ train $ B.words fox 

fox="The quick brown fox jumps over the brown fox who is slow jumps over the brown fox who is dead." 

Answer 5

Ecco una versione basata su foldl' che sembra essere circa due volte più veloce il vostro train:

train' :: [B.ByteString] -> Database 
train' xs = foldl' (flip f) M.empty $ zip3 xs (tail xs) (tail $ tail xs) 
    where 
    f (a, b, c) = M.insertWith (M.unionWith (+)) (a, b) (M.singleton c 1) 

ho provato su il Progetto Gutenberg Huckleberry Finn (che presumo sia il vostro 76.txt), e produce lo stesso risultato la vostra funzione. Il mio confronto temporale è stato molto poco scientifico, ma probabilmente questo approccio merita di essere visto.

Answer 6

Data.Map è progettato in base al presupposto che i confronti della classe Ord richiedano un tempo costante. Per le chiavi stringa questo potrebbe non essere il caso — e quando le stringhe sono uguali non è mai il caso. È possibile che tu stia colpendo questo problema a seconda di quanto è grande il tuo corpus e di quante parole hanno prefissi comuni.

Sarei tentato di provare una struttura dati progettata per funzionare con i tasti sequenza, come ad esempio un pacchetto bytestring-trie suggerito da Don Stewart.