13

先週、ユーザーMasseは、Haskellのディレクトリにファイルを再帰的にリストすることについて質問しました。List私が最初に考えたのは、パッケージのモナディックリストを使用して、印刷を開始する前にリスト全体をメモリに作成しないようにすることでした。私はこれを次のように実装しました：

module Main where

import Prelude hiding (filter) 
import Control.Applicative ((<$>))
import Control.Monad (join)
import Control.Monad.IO.Class (liftIO)
import Control.Monad.ListT (ListT)
import Data.List.Class (cons, execute, filter, fromList, mapL)
import System (getArgs)
import System.Directory (getDirectoryContents, doesDirectoryExist)
import System.FilePath ((</>))

main = execute . mapL putStrLn . listFiles =<< head <$> getArgs

listFiles :: FilePath -> ListT IO FilePath
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir
  where
    valid "."  = False
    valid ".." = False
    valid _ = True
    listIfDir False = return path
    listIfDir True
      =  cons path
      $  join
      $  listFiles
     <$> (path </>)
     <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path))

これは、すぐに印刷を開始し、メモリをほとんど使用しないという点で美しく機能します。FilePath -> IO [FilePath]残念ながら、同等のバージョンよりも数十倍遅くなります。

私は何が間違っているのですか？Listこのようなおもちゃの例以外のパッケージを使用したことListTがないので、どのようなパフォーマンスが期待できるかわかりませんが、40,000ファイルまでのディレクトリを処理するのに30秒（数分の1秒）もかかるようですスロー。

4

3 に答える 3

3

プロファイリングは、join（と一緒にdoesDirectoryExists）コード内のほとんどの時間を占めることを示しています。その定義がどのように展開するかを見てみましょう。

  join x
=> (definition of join in Control.Monad)
  x >>= id
=> (definition of >>= in Control.Monad.ListT)
  foldrL' mappend mempty (fmap id x)
=> (fmap id = id)
  foldrL' mappend mempty x

検索のルートディレクトリにkサブディレクトリがあり、その内容がすでにリストで計算されている場合：、適用後、（大まかに）次のようになります。時間がかかるので全部時間がかかります。ファイルの数がであり、それらが均等に分散されていると仮定すると、計算にかかる時間は、の最初のレベルのみになります。d1, d2, ... dkjoin(...(([] ++ d1) ++ d2) ... ++ dk)x ++ yO(length x)O(d1 + (d1 + d2) + ... + (d1 + ... dk-1))nd1 ... dkjoinO(n*k)listFiles

これが、ソリューションの主なパフォーマンスの問題だと思います。

于 2010-10-12T17:46:37.500 に答える
2

私は興味があります、logictを使用するために書かれた同じプログラムはあなたのためにどれくらいうまく機能しますか？ LogicTは意味的にはと同じですListTが、継続渡しスタイルで実装されているためconcat、発生していると思われる関連するタイプの問題が発生することはありません。

import Prelude hiding (filter)
import Control.Applicative
import Control.Monad
import Control.Monad.Logic
import System (getArgs)
import System.Directory (getDirectoryContents, doesDirectoryExist)
import System.FilePath ((</>))

main = sequence_ =<< observeAllT . fmap putStrLn . listFiles =<< head <$> getArgs

cons :: MonadPlus m => a -> m a -> m a
cons x xs = return x `mplus` xs

fromList :: MonadPlus m => [a] -> m a
fromList = foldr cons mzero

filter :: MonadPlus m => (a -> Bool) -> m a -> m a
filter f xs = do
  x <- xs
  guard $ f x
  return x

listFiles :: FilePath -> LogicT IO FilePath
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir
  where
    valid "."  = False
    valid ".." = False
    valid _ = True
    listIfDir False = return path
    listIfDir True
      =  cons path
      $  join
      $  listFiles
     <$> (path </>)
     <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path))
于 2010-10-14T00:36:57.267 に答える
1

大きなディレクトリで実行すると、メモリリークが発生します。これはgetDirectoryContentsの厳密さに関係していると思いますが、さらに進んでいる可能性があります。単純なプロファイリングはあまり効果がありませんでした。コストセンターをいくつか追加して、そこから移動します...

于 2010-10-12T16:46:05.780 に答える