如何更快列出目录？

我有几种情况需要递归列出文件，但是我的实现速度很慢。我有一个包含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

如何更快列出目录？

回答

相关问题