Escribiendo "wc -l" usando la biblioteca Iteratee - ¿cómo filtrar por nueva línea?

Question

Estoy tratando de encontrar el equivalente de "wc -l" usando la biblioteca Haskell Iteratee. A continuación se muestra el código para "WC" (que simplemente cuenta las palabras - similar al código de ejemplo iteratee en hackage), y corre muy rápido:

---

{-# LANGUAGE BangPatterns #-} 
import Data.Iteratee as I 
import Data.ListLike as LL 
import Data.Iteratee.IO 
import Data.ByteString 


length1 :: (Monad m, Num a, LL.ListLike s el) => Iteratee s m a 
length1 = liftI (step 0) 
    where 
    step !i (Chunk xs) = liftI (step $ i + fromIntegral (LL.length xs)) 
    step !i stream  = idone i stream 
{-# INLINE length1 #-} 
main = do 
    i' <- enumFile 1024 "/usr/share/dict/words" (length1 :: (Monad m) => Iteratee ByteString m Int) 
    result <- run i' 
    print result 
    {- Time measured on a linux x86 box: 
    $ time ./test ## above haskell compiled code 
    4950996 

    real 0m0.013s 
    user 0m0.004s 
    sys  0m0.007s 

    $ time wc -c /usr/share/dict/words 
    4950996 /usr/share/dict/words 

    real 0m0.003s 
    user 0m0.000s 
    sys  0m0.002s 
    -} 

---

Ahora, ¿cómo lo extiendes para contar el número de líneas que también corre rápido? Hice una versión usando Prelude.filter para filtrar solo "\ n" a la longitud, pero es más lento que Linux "wc -l" debido a demasiada memoria, y gc (evaluación lenta, supongo). Por lo tanto, escribí otra versión utilizando Data.ListLike.filter pero no va a compilar ya que no escribe cheque - ayudar aquí sería apreciada:

---

{-# LANGUAGE BangPatterns #-} 
    import Data.Iteratee as I 
    import Data.ListLike as LL 
    import Data.Iteratee.IO 
    import Data.ByteString 
    import Data.Char 
    import Data.ByteString.Char8 (pack) 

    numlines :: (Monad m, Num a, LL.ListLike s el) => Iteratee s m a 
    numlines = liftI $ step 0 
    where 
     step !i (Chunk xs) = liftI (step $i + fromIntegral (LL.length $ LL.filter (\x -> x == Data.ByteString.Char8.pack "\n") xs)) 
     step !i stream = idone i stream 
    {-# INLINE numlines #-} 

    main = do 
    i' <- enumFile 1024 "/usr/share/dict/words" (numlines :: (Monad m) => Iteratee ByteString m Int) 
    result <- run i' 
    print result 

Answer 1

Ya hay muchas buenas respuestas; Tengo muy poco que ofrecer en cuanto a rendimiento, pero algunos puntos de estilo.

En primer lugar, yo escribo de esta manera:

import Prelude as P 
import Data.Iteratee 
import qualified Data.Iteratee as I 
import qualified Data.Iteratee.IO as I 
import qualified Data.ByteString as B 
import Data.Char 
import System.Environment 

-- numLines has a concrete stream type so it's not necessary to provide an 
-- annotation later. It could have a more general type. 
numLines :: Monad m => I.Iteratee B.ByteString m Int 
numLines = I.foldl' step 0 
where 
    --step :: Int -> Word8 -> Int 
    step acc el = if el == (fromIntegral $ ord '\n') then acc + 1 else acc 

main = do 
    f:_ <- getArgs 
    words <- run =<< I.enumFile 65536 f numLines 
    print words 

La mayor diferencia es que esta utiliza Data.Iteratee.ListLike.foldl'. Tenga en cuenta que solo los elementos de flujo individuales son importantes para la función de paso, no el tipo de flujo. Es exactamente la misma función que usaría con, por ejemplo, Data.ByteString.Lazy.foldl'.

El uso de foldl' también significa que no necesita escribir iteratees manualmente con liftI. Desanimaría a los usuarios a hacerlo a menos que sea absolutamente necesario. El resultado suele ser más largo y más difícil de mantener con poco o ningún beneficio.

Finalmente, he aumentado significativamente el tamaño del búfer. En mi sistema, esto es marginalmente más rápido que enumerator s predeterminado de 4096, que es de nuevo marginalmente más rápido (con iteratee) que su elección de 1024. YMMV con esta configuración, por supuesto.

Answer 2

Si estás leyendo ByteString trozos, puede utilizar la función de countData.ByteString, el paso correspondiente sería entonces

step !i (Chunk xs) = liftI (step $ i + count 10 xs) 

(tal vez con un fromIntegral). Data.ByteString.count es bastante rápido, eso no debería ser mucho más lento que wc -l.

Answer 3

Así que hice algo de experimentación y obtuve un wc -l que es solo el doble de lento que "wc -l". Este es un mejor rendimiento que incluso la versión wc-c que se muestra arriba.

{-# LANGUAGE OverloadedStrings #-} 

import qualified Data.ByteString.Lazy.Char8 as BSL 
import qualified Data.ByteString.Char8 as BS 
import qualified Data.Enumerator as E 
import qualified Data.Enumerator.Binary as EB 
import Control.Monad.IO.Class (liftIO) 
import Data.Int 

numlines :: Int64 -> E.Iteratee BS.ByteString IO() 
numlines n = do 
    chunk <- EB.take 1024 
    case chunk of 
     "" -> do liftIO $ print n 
       return() 
     a -> do let ct = BSL.count '\n' a 
       numlines (n+ct) 

main = do 
    let i = EB.enumFile "/usr/share/dict/words" E.$$ numlines 0 
    E.run_ i 

Ejecutarlo vs orígenes:

Eriks-MacBook-Air:skunk erikhinton$ time wc -l "/usr/share/dict/words" 
    235886 /usr/share/dict/words 

real 0m0.009s 
user 0m0.006s 
sys 0m0.002s 
Eriks-MacBook-Air:skunk erikhinton$ time ./wcl 
235886 

real 0m0.019s 
user 0m0.013s 
sys 0m0.005s 

[EDIT]

He aquí un aún más rápido, más pequeño tamaño y forma mucho más concisa/expresiva de hacerlo. Estos enumeradores comienzan a divertirse.

{-# LANGUAGE OverloadedStrings #-} 

import qualified Data.ByteString.Lazy.Char8 as BSL 
import qualified Data.ByteString.Char8 as BS 
import qualified Data.Enumerator as E 
import qualified Data.Enumerator.Binary as EB 
import qualified Data.Enumerator.List as EL 
import Control.Monad.IO.Class (liftIO) 
import Data.Int 

numlines :: E.Iteratee BS.ByteString IO() 
numlines = do 
      num <- EL.fold (\n b -> (BS.count '\n' b) + n) 0 
      liftIO . print $ num 

main = do 
    let i = EB.enumFile "/usr/share/dict/words" E.$$ numlines 
    E.run_ i 

Y el momento

Eriks-MacBook-Air:skunk erikhinton$ time ./wcl2 
235886 

real 0m0.015s 
user 0m0.010s 
sys 0m0.004s 

Answer 4

me di cuenta de cómo solucionar el error de tipo. La clave de error de tipo de fijación es la comprensión de la relación entre Data.ListLike.filter y ByteString de entrada que se pasa a ese filtro. Aquí está el tipo de Data.ListLike.filter:

Data.ListLike.filter 
:: Data.ListLike.Base.ListLike full item => 
(item -> Bool) -> full -> full 

completa se refiere a la corriente en el contexto de un empadronador/iteratee, si he entendido bien. elemento se refiere al elemento de la secuencia.

Ahora, si queremos filtrar en nueva línea en el archivo de entrada, tenemos que saber el tipo de flujo de archivos de entrada y el tipo de elementos en esa secuencia. En este caso, el archivo de entrada se lee como ByteString transmisión.ByteString está documentado como una representación eficiente del espacio de un vector Word8. Por lo tanto, elemento escriba aquí es Word8.

Así, cuando escribimos el filtro, en la función de paso, hay que asegurarse de que la operación Bool se define para Word8 ya que es el tipo de elemento que se pasa al filtro (como se explicó anteriormente). Estamos filtrando por nueva línea. Por lo tanto, la función bool como la de abajo que construye una representación Word8 de nueva línea, y comprobar la igualdad contra la x del tipo Word8, debería funcionar:

\x -> x == Data.ByteString.Internal.c2w '\n' 

Todavía hay una pieza más que falta - por algunas razones, la compilador (v7.0.3 Mac) no puede deducir el tipo de el en la firma de tipo numfile (si alguien tiene ideas sobre por qué es así, por favor discuta). Así, diciéndole explícitamente que es Word8 resuelve el problema de compilación:

numlines :: (Monad m, Num a, LL.ListLike s Word8) => Iteratee s m a 

código completo abajo - que compila y corre bastante rápido.

{-# LANGUAGE BangPatterns,FlexibleContexts #-} 
import Data.Iteratee as I 
import Data.ListLike as LL 
import Data.Iteratee.IO 
import Data.ByteString 
import GHC.Word (Word8) 
import Data.ByteString.Internal (c2w) 

numlines :: (Monad m, Num a, LL.ListLike s Word8) => Iteratee s m a 
numlines = liftI $ step 0 
    where 
    step !i (Chunk xs) = let newline = c2w '\n' in liftI (step $i + fromIntegral (LL.length $ LL.filter (\x -> x == newline) xs)) 
    step !i stream = idone i stream 
{-# INLINE numlines #-} 


main = do 
    i' <- enumFile 1024 "/usr/share/dict/words" (numlines :: (Monad m) => Iteratee ByteString m Int) 
    result <- run i' 
    print result 
{- Time to run on mac OSX: 

$ time ./test ## above compiled program: ghc --make -O2 test.hs 
235886 

real 0m0.011s 
user 0m0.007s 
sys 0m0.004s 
$ time wc -l /usr/share/dict/words 
235886 /usr/share/dict/words 

real 0m0.005s 
user 0m0.002s 
sys 0m0.002s 
-}