Написание "wc -l" с использованием библиотеки Iteratee - как отфильтровать строки?

Question

Я пытаюсь найти эквивалент "wc -l", используя библиотеку Haskell Iteratee.Ниже приведен код для "wc" (который просто подсчитывает слова - аналогично коду в итеративном примере по взлому) и работает очень быстро:

---

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

---

Теперь, как сделатьВы расширяете его, чтобы посчитать количество строк, которые тоже работает быстро?Я сделал версию, используя Prelude.filter для фильтрации только "\ n" по длине, но она медленнее, чем linux "wc -l" из-за слишком большого количества памяти, и gc (ленивая оценка, я полагаю).Итак, я написал другую версию, используя Data.ListLike.filter, но она не будет компилироваться, потому что она не проверяет тип - здесь приветствуется помощь:

---

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

Итак, я немного поэкспериментировал и получил wc -l, который примерно в два раза медленнее, чем "wc -l". Это лучшая производительность, чем даже версия wc -c, показанная выше.

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

Запуск по сравнению с родным:

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]

Вот еще более быстрый, компактный и гораздо более краткий и выразительный способ сделать это. Эти счетчики начинают веселиться.

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

И сроки

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

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

Answer 2

Уже есть много хороших ответов; У меня очень мало предложений по производительности, но есть несколько стилей.

Во-первых, я бы написал так:

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

Самая большая разница в том, что здесь используется Data.Iteratee.ListLike.foldl'. Обратите внимание, что для функции шага важны только отдельные элементы потока, а не тип потока. Это та же самая функция, которую вы использовали бы, например, с. Data.ByteString.Lazy.foldl'.

Использование foldl' также означает, что вам не нужно вручную писать итерации с liftI. Я бы не рекомендовал пользователям делать это, если в этом нет крайней необходимости. Результат, как правило, дольше и его сложнее поддерживать практически без пользы.

Наконец, я значительно увеличил размер буфера. В моей системе это немного быстрее, чем enumerator s по умолчанию 4096, что опять же незначительно быстрее (с iteratee), чем ваш выбор 1024. YMMV с этой настройкой, конечно.

Answer 3

Я разобрался, как исправить ошибку типа.Ключом к исправлению ошибки типа является понимание взаимосвязи между Data.ListLike.filter и ByteString входными данными, которые передаются этому фильтру,Вот тип Data.ListLike.filter:

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

full относится к потоку в контексте перечислителя / итератора, если я его понимаюправильно. item относится к элементу потока.

Теперь, если мы хотим выполнить фильтрацию по новой строке во входном файле, мы должны знать тип потока входного файла и тип элементов в этом потоке.В этом случае входной файл читается как ByteString stream. ByteString задокументировано как эффективное для пространства представление вектора Word8.Итак, тип item здесь - Word8.

Итак, когда мы пишем фильтр, в функции шага мы должны убедиться, что операция Bool определена для Word8, поскольку это типэлемента, передаваемого в фильтр (как описано выше).Мы фильтруем новую строку.Таким образом, функция bool, подобная приведенной ниже, которая создает представление новой строки в Word8 и проверяет равенство x для типа Word8, должна работать:

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

Еще одна недостающая часть - по некоторым причинамкомпилятор (v7.0.3 Mac) не может определить тип el в сигнатуре типа numfile (если у кого-то есть идеи, почему это так, пожалуйста, обсудите).Итак, явное указание на то, что Word8 решает проблему компиляции:

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

Полный код ниже - он компилируется и работает довольно быстро.

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

Answer 4

Если вы читаете чанки ByteString, вы можете использовать функцию count из Data.ByteString, тогда соответствующий шаг будет

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

(возможно, с fromIntegral).Data.ByteString.count довольно быстрый, он не должен быть слишком медленным, чем wc -l.