7

Haskell Iteratee ライブラリを使用して、「wc -l」に相当するものを考え出そうとしています。以下は "wc" のコード (単語をカウントするだけです - ハックの iteratee の例のコードに似ています) で、非常に高速に実行されます:

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

4 に答える 4

3

それで私はいくつかの実験を行い、「wc -l」の約 2 倍しか遅い 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

[編集]

これは、さらに高速でフットプリントが小さく、はるかに簡潔で表現力豊かな方法です。これらの列挙子は面白くなり始めています。

{-# 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
于 2011-11-03T03:26:37.953 に答える
1

ByteStringチャンクを読んでいる場合は、countから関数を使用できます。Data.ByteString関連するステップは次のようになります

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

(おそらく fromIntegral を使用)。Data.ByteString.countwc -l よりも遅くはありません。

于 2011-11-02T20:01:03.270 に答える
1

すでに多くの良い答えがあります。パフォーマンスに関して提供できるものはほとんどありませんが、いくつかのスタイル ポイントがあります。

まず、次のように書きます。

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'. ストリームの種類ではなく、個々のストリーム要素のみがステップ関数に関係することに注意してください。これは、eg で使用する関数とまったく同じですData.ByteString.Lazy.foldl'。

を使用foldl'するということは、 iteratees を使用して手動で記述する必要がないことも意味しますliftI。絶対に必要な場合を除き、ユーザーがそうするのを思いとどまらせます。通常、結果は長くなり、維持するのが難しくなり、メリットはほとんどまたはまったくありません。

最後に、バッファ サイズを大幅に増やしました。私のシステムenumeratorでは、これはデフォルトの 4096 よりもわずかに高速です。これは、選択した 1024 よりもわずかに高速です (反復を使用)。もちろん、この設定の YMMV。

于 2011-11-03T19:17:40.810 に答える
1

タイプエラーを修正する方法を見つけました。型エラーを修正するための鍵は、 Data.ListLike.filter とそのフィルターに渡される ByteString入力との関係を理解することです。Data.ListLike.filter のタイプは次のとおりです。

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

私が正しく理解していれば、フルは列挙子/反復子のコンテキストでストリームを参照します。itemはストリームの要素を参照します。

ここで、入力ファイルの改行でフィルタリングする場合は、入力ファイル ストリームのタイプと、そのストリーム内の要素のタイプを知る必要があります。この場合、入力ファイルはByteStringストリームとして読み込まれます。ByteStringは、Word8 ベクトルのスペース効率の高い表現として文書化されています。というわけで、ここのアイテムタイプはWord8です。

そのため、ステップ関数でフィルターを記述するときは、ブール演算が Word8 に対して定義されていることを確認する必要があります。これは、フィルターに渡されるアイテムのタイプであるためです (上記で説明したように)。改行をフィルタリングしています。したがって、改行の Word8 表現を構築し、Word8 型の x と等しいかどうかをチェックする以下のような bool 関数が機能するはずです。

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

まだもう 1 つ欠けている部分があります - 何らかの理由で、コンパイラ (v7.0.3 Mac) はnumfile 型シグネチャのelの型を推測できません (その理由について何かアイデアがある場合は、議論してください)。したがって、それが 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
-}
于 2011-11-03T11:03:39.810 に答える