Pregunta Construyendo un histograma con haskell, muchas veces más lento que con python


Iba a probar la clasificación ingenua bayes. Una parte de esto iba a construir un histograma de los datos de entrenamiento. El problema es que estoy usando una gran cantidad de datos de entrenamiento, la lista de correo de haskell-cafe desde hace un par de años, y hay más de 20k archivos en la carpeta.

Lleva un tiempo más de dos minutos crear el histograma con python y algo más de 8 minutos con haskell. Estoy usando Data.Map (insertWith '), enumeradores y texto. ¿Qué más puedo hacer para acelerar el programa?

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

Pitón:

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

Editar: Importaciones adicionales


13
2018-03-19 14:34


origen


Respuestas:


Puede intentar usar mapas hash imperativos del paquete de tablas hash: http://hackage.haskell.org/package/hashtables Recuerdo que una vez obtuve una aceleración moderada en comparación con Data.Map. Sin embargo, no esperaría nada espectacular.

ACTUALIZAR

Simplifiqué tu código python para poder probarlo en un solo archivo grande (100 millones de líneas):

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")

Toma 6.06 segundos

Traducción de Haskell usando 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 

Ejecutar con un área de asignación grande: histogram +RTS -A500M Toma 9.3 segundos, con 2.4% GC. Todavía bastante más lento que Python, pero no está mal.

De acuerdo con la Guía de usuario de GHC, puede cambiar las opciones de RTS al compilar:

GHC le permite cambiar las opciones predeterminadas de RTS para un programa en compilación   hora, usando el indicador -with-rtsopts (Sección 4.12.6, "Opciones que afectan   enlace"). Un uso común para esto es darle a su programa un valor predeterminado   montón y / o tamaño de pila que es mayor que el predeterminado. Por ejemplo,   para establecer -H128m -K64m, vincular con -with-rtsopts = "- H128m -K64m".


8
2018-03-19 17:14



Sus implementaciones de Haskell y Python están usando mapas con diferentes complejidades. Los diccionarios de Python son mapas hash, por lo que el tiempo esperado para cada operación (prueba de membresía, búsqueda e inserción) es O (1). La versión de Haskell usa Data.Map, que es un árbol de búsqueda binaria equilibrada, por lo que las mismas operaciones toman el tiempo O (lg n). Si cambias tu versión de Haskell para usar una implementación de mapa diferente, digamos una tabla hash o algún tipo de trie, debería ser mucho más rápido. Sin embargo, no estoy lo suficientemente familiarizado con los diferentes módulos que implementan estas estructuras de datos para decir cuál es el mejor. Yo comenzaría con la categoría Datos en Hackage y busca uno que te guste También puede buscar un mapa que permita actualizaciones destructivas como STArray hace.


7
2018-03-19 15:22



Necesitamos más información:

  • ¿Cuánto tardan los dos programas en procesar las palabras de la entrada, sin estructura de datos para mantener conteos?

  • ¿Cuántas palabras distintas hay, para que podamos juzgar si el extra log N costo para árboles balanceados es una consideración?

  • ¿Qué dice el generador de perfiles de GHC? En particular, ¿cuánto tiempo se dedica a la asignación? Es posible que la versión de Haskell pase la mayor parte del tiempo asignando nodos de árbol que se vuelven obsoletos rápidamente.

  • ACTUALIZAR: Me perdí que el "texto" en minúscula podría significar Data.Text. Puede estar comparando aplica y naranjas. La codificación Latin1 de Python usa un byte por char. Aunque intenta ser eficiente, Data.Text debe permitir la posibilidad de más de 256 caracteres. ¿Qué pasa si cambias a String, o mejor, Data.ByteString?

Dependiendo de lo que digan estos indicadores, aquí hay un par de cosas para probar:

  • Si analizar la entrada es un cuello de botella, intente manejar todas sus E / S y análisis de Data.ByteString en lugar de Text.

  • Si la estructura de datos es un cuello de botella, Bentley y Sedgewick árboles ternarios de búsqueda son puramente funcionales, pero funcionan competentemente con tablas hash. Hay un TernaryTrees paquete en Hackage.


5
2018-03-19 17:41