リストパッケージのモナディックリストを使用しているのはなぜですか？

StackOverflow https://stackoverflow.com/questions/3916444

質問

先週、ユーザーマスは尋ねました 再帰的にファイルをリストすることについての質問 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 このようなおもちゃの例以外では、どのようなパフォーマンスを期待するかはわかりませんが、30秒（わずか数秒で、40,000のファイルを持つディレクトリを処理するための処理が遅すぎるようです。

役に立ちましたか？

解決

プロファイリングはそれを示しています 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, ... dk, 、申請後 join あなたは（大まかに）得る： (...(([] ++ d1) ++ d2) ... ++ dk). 。以来 x ++ y 時間がかかります O(length x) 全体に時間がかかります O(d1 + (d1 + d2) + ... + (d1 + ... dk-1)). 。ファイルの数があると仮定した場合 n そして、それらは均等に分布しています d1 ... dk その後、計算する時間 join だろう O(n*k) そして、それは最初のレベルのためだけです listFiles.

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

他のヒント

私は興味があります、同じプログラムが使用するためにどれだけうまく書かれていますか ロジクト あなたのために働いていますか？ 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))

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top