2010-05-26 16 views
16

Estoy tratando de aprender Haskell y después de un artículo en reddit sobre las cadenas de texto de Markov, decidí implementar la generación de texto de Markov primero en Python y ahora en Haskell. Sin embargo, noté que mi implementación de Python es mucho más rápida que la versión de Haskell, incluso Haskell está compilada con código nativo. Me pregunto qué debo hacer para que el código Haskell funcione más rápido y por ahora creo que es mucho más lento porque utilizo Data.Map en lugar de hashmaps, pero no estoy seguroOptimizar el código Haskell

Voy a publicar el código Python y Haskell también. Con los mismos datos, Python tarda alrededor de 3 segundos y Haskell está más cerca de 16 segundos.

No hace falta decir que voy a tomar cualquier crítica constructiva :).

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." 
+1

Interesante, también en busca de la respuesta. 16 versus 3 segundos es realmente una gran diferencia. – wvd

+0

La sangría parece haber sido destrozada por el código de Python, por cierto ... –

+1

No creo que su código Haskell logre lo que usted quiere. Si comprueba el resultado, verá que no hay valores mayores que 2 en los mapas 'M.Map String Int'. ¿Quiere decir 'n + o' o' o + 1' en lugar de 'n + 1'? –

Respuesta

7

Traté de evitar hacer algo sofisticado o sutil. Estos son solo dos enfoques para hacer la agrupación; el primero enfatiza la coincidencia de patrones, el segundo 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" 

creo que son tanto más rápido que la versión original, pero la verdad es que sólo les intentado contra el primer corpus razonable que encontré.

EDITAR Según punto muy válido de 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 
+0

Como me importa el estilo, creo que es mejor usar algo más específico que 'alterar' aquí. Sabemos que nunca necesitaremos borrado en esta situación, y tener que agregar 'Just' de esta manera afecta la legibilidad. –

+0

Lo siento por la respuesta tardía. ¿Podría explicar también por qué es una solución más rápida? Básicamente, ambos hacen lo mismo, a excepción de la compresión y la caída. – Masse

11

a) ¿Cómo estás compilando ella? (ghc -O2?)

b) ¿Qué versión de GHC?

c) Data.Map es bastante eficiente, pero puede engañarse con actualizaciones vagas: use insertWith ', no insertWithKey.

d) No convierta cadenas de bytes en Cadena. Guárdelos como cadenas de bytes y almacénelos en el Mapa

+0

La versión es 6.12.1. Con su ayuda, pude exprimir 1 segundo del tiempo de ejecución, pero todavía está lejos de la versión de Python. – Masse

1

Como sugirió Don, estudie el uso de las versiones más estrictas de sus funciones: insertWithKey '(y M.insertWith' ya que ignora el parámetro de clave la segunda vez).

Parece que su código probablemente acumule muchos bloqueos hasta que llegue al final de su [String].

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

... trata sobre todo de graficar el montón (a mitad de camino a través del capítulo). Interesado en ver lo que descubres.

+0

Hice los cambios sugeridos por Don Stewart. Anteriormente, el código tomaba de 41 a 44 megabytes de memoria, ahora solo demora 29. La representación gráfica de la memoria muestra que TSO toma la mayor parte de la memoria, luego viene GHC.types y luego los otros tipos de datos utilizados en el código. La memoria aumenta rápidamente en todas las secciones durante un segundo. Después de que un segundo TSO y GHC.types sigan aumentando, todos los demás comienzan a retroceder lentamente. (Si estoy leyendo el gráfico a la derecha) – Masse

2

1) No tengo claro tu código. a) Usted define "zorro" pero no lo usa. ¿Querías que intentáramos ayudarte usando "zorro" en lugar de leer el archivo? b) Usted declara esto como "módulo Markov" y luego tiene un 'principal' en el módulo. c) System.Random no es necesario. Nos ayuda a ayudarlo si limpia el código un poco antes de publicarlo.

2) Use ByteStrings y algunas operaciones estrictas como Don dijo.

3) Compile con -O2 y use -fforce-recomp para asegurarse de que realmente compiló el código.

4) Pruebe esta ligera transformación, funciona muy rápido (0.005 segundos). Obviamente, la entrada es absurdamente pequeña, por lo que necesitaría proporcionar su archivo o simplemente probarlo usted mismo.

{-# 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." 
+0

Bueno, sí, soy un principiante como dice la etiqueta: P. No me di cuenta de las consecuencias de nombrar el módulo algo más que Main. Y el zorro se usó para probar el algoritmo. Es más fácil verificar la entrada pequeña que la entrada de un libro completo – Masse

3

Aquí hay una versión basada en foldl' que parece ser aproximadamente el doble de rápido que el 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) 

lo probé en el Proyecto Gutenberg Huckleberry Finn (que supongo que es su 76.txt), y produce el mismo resultado que su función. Mi comparación de tiempo fue muy poco científica, pero este enfoque probablemente valga la pena echarle un vistazo.

8

Data.Map está diseñado bajo el supuesto de que las comparaciones de la clase Ord toman un tiempo constante. Para las claves de cadena, este puede no ser el caso — y cuando las cadenas son iguales, nunca es el caso. Puede o no estar abordando este problema dependiendo de qué tan grande es su corpus y cuántas palabras tienen prefijos comunes.

Estaría tentado de probar una estructura de datos diseñada para operar con claves de secuencia, como por ejemplo un paquete bytestring-trie amablemente sugerido por Don Stewart.

+3

¿Una cadena de bytes? http://hackage.haskell.org/package/bytestring-trie –

+0

@don: gracias por la actualización. Estoy convencido de que conoces al menos el 60% de los contenidos de hackage por nombre :-) –

Cuestiones relacionadas