Scrittura "wc -l" usando la libreria Iteratee - come filtrare per newline?

Question

Sto provando a inventare l'equivalente di "wc -l" usando la libreria Haskell Iteratee. Di seguito è riportato il codice per "wc" (che solo conta le parole - simile al codice dell'esempio iteratee su hackage), e corre molto veloce:

---

{-# 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 
    -} 

---

Ora, come si fa lo estendi per contare il numero di linee troppo veloci? Ho fatto una versione usando Prelude.filter per filtrare solo "\ n" in lunghezza ma è più lento di linux "wc -l" a causa della troppa memoria, e gc (valutazione pigra, immagino). Così, ho scritto un'altra versione utilizzando Data.ListLike.filter ma non compilerà perché non digita check - aiuto qui sarebbe apprezzato:

---

{-# 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

Ci sono già molte buone risposte; Ho molto poco da offrire in termini di prestazioni, ma alcuni punti di stile.

In primo luogo, vorrei scrivere in questo modo:

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 più grande differenza è che questo utilizza Data.Iteratee.ListLike.foldl'. Si noti che solo i singoli elementi del flusso sono importanti per la funzione passo, non il tipo di flusso. È esattamente la stessa funzione che utilizzeresti ad es. Data.ByteString.Lazy.foldl'.

Utilizzare foldl' significa anche che non è necessario scrivere manualmente iterate con liftI. Scorporrei gli utenti dal farlo, a meno che non sia assolutamente necessario. Il risultato è solitamente più lungo e difficile da mantenere con poco o nessun beneficio.

Infine, ho aumentato la dimensione del buffer in modo significativo. Sul mio sistema questo è leggermente più veloce del valore predefinito dis di 4096, che è ancora marginalmente più veloce (con iteratee) rispetto alla scelta di 1024. YMMV con questa impostazione ovviamente.

Answer 2

Se stai leggendo ByteString pezzi, è possibile utilizzare la funzione count dal Data.ByteString, il passo in questione sarebbe quindi

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

(magari con una fromIntegral). Data.ByteString.count è piuttosto veloce, che non dovrebbe essere troppo più lento di wc -l.

Answer 3

Così ho fatto qualche esperimento e ho ottenuto un wc -l che è solo circa il doppio di "wc -l" Questa è una prestazione migliore rispetto alla versione wc -c mostrata sopra.

{-# 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 

L'esecuzione vs origini:

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]

Ecco un, impronta ancora più veloce e più piccolo modo molto più conciso/espressiva di farlo. Questi enumeratori stanno iniziando a divertirsi.

{-# 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 

E i tempi

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

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

Answer 4

ho capito come risolvere l'errore di tipo. La chiave per errore tipo di fissaggio è capire il rapporto tra Data.ListLike.filter e ByteString ingresso che si passa al filtro. Ecco il tipo di Data.ListLike.filter:

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

piena si riferisce al flusso nel contesto di un enumeratore/iteratee, se ho capito bene. articolo si riferisce all'elemento del flusso.

Ora, se vogliamo filtrare su newline nel file di input, dobbiamo conoscere il tipo di flusso di file di input e il tipo di elementi in quel flusso. In questo caso, il file di input viene letto come stream ByteString.ByteString è documentato come rappresentazione efficiente sotto il profilo dello spazio di un vettore Word8. Quindi, il tipo item qui è Word8.

Quindi, quando scriviamo il filtro, nella funzione di passo, dobbiamo assicurarci che l'operazione di Bool sia definita per Word8 poiché questo è il tipo di oggetto che viene passato al filtro (come spiegato sopra). Stiamo filtrando per newline. Quindi, la funzione bool come quella qui sotto, che costruisce una rappresentazione Word8 di ritorno a capo, e controllare per l'uguaglianza contro x di tipo Word8, dovrebbe funzionare:

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

C'è ancora un altro pezzo mancante - per alcuni motivi, il compiler (v7.0.3 Mac) non è in grado di dedurre il tipo di el nella firma del tipo numfile (se qualcuno ha idee sul perché è così, per favore discutine). Quindi, dicendo esplicitamente che si tratta Word8 risolve il problema di compilazione:

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

codice completo qui sotto - si compila, e corre abbastanza veloce.

{-# 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 
-}