爲什麼我的代碼使用List包中的monadic列表太慢？

上週，用戶Masse在Haskell的一個目錄中詢問question about recursively listing files。我的第一個想法是嘗試使用來自List package的monadic列表，以避免在打印開始之前在內存中構建整個列表。我實現這個如下：爲什麼我的代碼使用List包中的monadic列表太慢？

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]版本慢了幾十倍。

我在做什麼錯？我從來沒有使用過像這樣的玩具例子中的包ListT，所以我不知道期望的性能是什麼樣的，但是30秒（而不是幾分之一秒）處理具有〜40,000個文件的目錄似乎太慢了。

來源

2010-10-12 Travis Brown

我們可以使用'Data.ByteString.getDirectoryContents :: ByteString - > [ByteString]'。如果考慮40,000個文件，每個文件包含10個以上的字符，那就是400,000個字符。 Haskell中的[Char]需要什麼？ Ballpark 12字節（x86）或24（x86-64）。所以這400,000個字符在整個鏈表中都是8MB或更多。現在我已經說了所有這些，希望你會回答「我已經對getDirectoryContents進行了基準測試，這不是問題」。 – 2010-10-12 17:43:02

@TomMD：我主要對使用'getDirectoryContents'的FilePath - > IO [FilePath]'版本進行比較的方式完全相同（例如，Masse的原始實現）。所以我不認爲這是問題，但我會看看。 – 2010-10-12 22:28:54

分析顯示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子目錄及其內容在列表中已經計算：d₁, d₂, ... d_k，然後應用join後，你會得到（大約）： (...(([] ++ d₁) ++ d₂) ... ++ d_k)。由於x ++ y需要時間O(length x)整件事情需要時間O(d₁ + (d₁ + d₂) + ... + (d₁ + ... d_k-1))。如果我們假設文件數量爲n，並且它們均勻分佈在d₁ ... d_k之間，那麼計算join的時間將爲O(n*k)，並且僅用於第一級listFiles。

我認爲這是解決方案的主要性能問題。

來源

2010-10-12 17:46:37

Masse原始實現中的'concat'（這個速度要快得多）似乎是做了完全相同的事情，但我會更詳細地研究這一點。 – 2010-10-12 22:32:23

Concat通過融合規則轉化爲以下內容，但我不清楚它是否一定更快，而且我現在還沒有達到基準測試：''concat「forall xs。 concat xs = build（\ c n - > foldr（\ x y - > foldr c y x）n xs）' – sclv 2010-10-13 03:29:52

同時發表評論。ListT定義了它自己的列表類型，所以在它的所有操作中都增加了一些間接性。 – 2010-10-13 06:03:23

在大目錄上運行它會導致內存泄漏。我懷疑這與getDirectoryContents的嚴格性有關，但可能會有更多的事情發生。簡單的分析並沒有太多的變化，我想添加一些額外的成本中心，並從那裏...

來源

2010-10-12 16:46:05 sclv

我很好奇，用相同的程序編寫使用logict爲你工作？ LogicT在語義上與ListT相同，但是以continuation-passing樣式實現，因此它不應該具有您似乎遇到的與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-14 00:36:57

爲什麼我的代碼使用List包中的monadic列表太慢？

回答

相關問題