如何更快列出目錄？

我有幾種情況需要遞歸列出文件，但是我的實現速度很慢。我有一個包含92784個文件的目錄結構。 find在不到0.5秒的時間內列出了這些文件，但是我的Haskell實現速度要慢很多。如何更快列出目錄？

我的第一個實施需要9秒多的時間才能完成，下一個版本超過5秒，而我目前的時間少於2秒。

listFilesR :: FilePath -> IO [FilePath] 
listFilesR path = let 
    isDODD "." = False 
    isDODD ".." = False 
    isDODD _ = True 

    in do 
     allfiles <- getDirectoryContents path 
    dirs <- forM allfiles $ \d -> 
     if isDODD d then 
     do let p = path </> d 
      isDir <- doesDirectoryExist p 
      if isDir then listFilesR p else return [d] 
     else return [] 
    return $ concat dirs

測試約需100兆字節的存儲器（+ RTS -s），並且該程序在GC花費40％左右。

我正在考慮在WriterT monad中使用Sequence作爲monoid來阻止concats和list的創建。這可能有助於嗎？我還應該做什麼？

編輯：我編輯了使用readDirStream的函數，它有助於減少內存。仍然有一些分配發生，但生產率現在大於95％，並且運行時間不到一秒鐘。

這是當前版本：

list path = do 
    de <- openDirStream path 
    readDirStream de >>= go de 
    closeDirStream de 
    where 
    go d [] = return() 
    go d "." = readDirStream d >>= go d 
    go d ".." = readDirStream d >>= go d 
    go d x = let newpath = path </> x 
     in do 
      e <- doesDirectoryExist newpath 
      if e 
     then 
      list newpath >> readDirStream d >>= go d 
     else putStrLn newpath >> readDirStream d >>= go d

來源

2010-10-07 Masse

我認爲System.Directory.getDirectoryContents構造了一個完整的列表，因此使用了很多內存。如何使用System.Posix.Directory？ System.Posix.Directory.readDirStream一個接一個返回一個條目。

此外，FileManip library可能是有用的，雖然我從來沒有使用它。

來源

2010-10-07 17:59:15

我做了一個使用System.Posix.Directory的版本並進行迭代，如果有更好的方法，它沒有太多的工作。我發現一件奇怪的事情是System.Posix.Directory似乎沒有提供我期望的功能。「readdir」返回一個指向「struct dirent」的指針，但它似乎是唯一可以從DirectoryStream獲得的是文件名 - 這意味着你必須再次調用（可能是通過使用doesDirectoryExist的stat（））來查找是否這是一個目錄。這也可能是問題的一部分 - 找到並不需要另一個系統調用來發現它是否是一個目錄。 – mokus 2010-10-07 23:09:49

@mokus：感謝您的信息。在Posix系統中，由[readdir]（http://www.opengroup.org/onlinepubs/009695399/functions/readdir.html）讀取目錄不會返回返回的條目是否是目錄，因此您需要單獨系統調用（通常是stat或lstat）來決定它是否是一個目錄。因此，您描述的System.Posix.Directory的行爲並不奇怪。 find命令的一些實現使用硬鏈接計數技巧來省略對stat的不必要調用，這使得遍歷速度更快。 – 2010-10-08 00:52:21

在我的系統（Mac OS）上，「struct dirent」有一個字段「d_type」，其中一個可能的值是「DT_DIR」。維基百科提示這在POSIX規範中是可選的，但它肯定會是DirectoryStream提供'isDir'或'fileType'操作的一個強有力的例子，如果可用則使用該信息，否則調用stat。即使它不是必需的標準，如果他的平臺有它，如果發現不使用它，我會感到震驚。 – mokus 2010-10-08 01:01:54

的一個問題是，它構建的目錄內容的完整列表，使程序能夠它們做任何事情。惰性IO通常會被忽視，但是在這裏使用unsafeInterleaveIO可以顯着減少內存使用。

listFilesR :: FilePath -> IO [FilePath] 
listFilesR path = 
    let 
    isDODD "." = False 
    isDODD ".." = False 
    isDODD _ = True 
    in unsafeInterleaveIO $ do 
    allfiles <- getDirectoryContents path 
    dirs <- forM allfiles $ \d -> 
     if isDODD d then 
     do let p = path </> d 
      isDir <- doesDirectoryExist p 
      if isDir then listFilesR p else return [d] 
     else return [] 
    return $ concat dirs

來源

2010-10-07 13:53:28 sabauma

削減了大約0.4秒和20兆字節。所以更好一點 – Masse 2010-10-07 14:29:28

分析您的代碼表明大部分CPU時間都在getDirectoryContents,doesDirectoryExist和</>之間。這意味着只有改變數據結構纔不會有太大的幫助。如果你想匹配find的性能，你應該使用較低級別的函數來訪問文件系統，可能是Tsuyoshi指出的。

來源

2010-10-07 19:03:42

是否可以使用某種緩存系統與讀取結合使用？我正在考慮一個異步索引服務/線程，以保持此緩存在後臺保持最新，也許您可以將緩存作爲一個簡單的SQL-DB進行處理，然後在對它進行查詢時爲您提供一些很好的性能？

您能否詳細闡述一下您的「項目/想法」，以便我們能夠提出一些替代方案？

我自己不會去做一個「完全索引」，因爲我主要是建立基於web的服務，而「resposnetime」對我很重要，另一方面 - 如果它啓動一個新服務器的初始方式我確信顧客不會介意第一次等待。我只是將結果存儲在數據庫中供以後查找。

來源

2010-10-07 23:04:36 BerggreenDK

我總是接受新的想法。我正在爲Hyper Estraier寫一個包裝，一個全文搜索引擎，供桌面使用。我是一個沉重的命令行用戶，所以我正在考慮做一個本地收集器和搜索器。目前我已將我的bash腳本轉換爲Haskell，但它仍然使用estcmd命令進行收集和搜索，並且系統過程調用很難看。對於本地採集者，我需要至少在第一遍時解析每個文件。但我想不出一種方法來列出自上次以來添加或修改的文件。 – Masse 2010-10-08 04:19:20

好的 - 你有什麼樣的操作系統？例如。 Windows對新文件有「目錄事件」，重命名等等，如果你有某種「根」文件夾，你可以通過遞歸觸發來放置一個「根事件處理程序」。還沒有嘗試過，但是我會在第一次編制目錄後尋找那個方向。 – BerggreenDK 2010-10-09 01:34:09

Linux具有全局文件緩存，因此您不必編寫一個文件，並且它在應用程序之間共享。它也有目錄事件。 – 2012-09-04 21:49:31

如何更快列出目錄？

回答

相關問題