algorithm - 具有大量文件的目录结构的树遍历算法

Question

当递归遍历目录结构时，如果文件多于目录，使用什么算法最有效？我注意到当使用深度优先遍历时，当给定目录中有很多文件时，它似乎需要更长的时间。在这种情况下，广度优先遍历是否更有效？我目前无法描述这两种算法，因此非常欢迎您的见解。

编辑：响应 alphazero 的评论，我在 Linux 机器上使用 PHP。

Answer 1

由于您的文件多于目录，因此看起来好像您正在处理嵌套非常深的目录，这会使 DFS 比 BFS 占用更多的内存（因此需要更多的时间）。本质上，BFS 和 DFS 都做同样的事情（即访问图表的每个节点），因此通常它们的速度不应有任何显着差异。

如果没有实际看到您的实现，很难说为什么您的 DFS 会变慢。由于文件系统中的链接/快捷方式，您确定不会多次访问相同的节点吗？如果您使用基于显式堆栈的 DFS 而不是递归，您也可能会获得显着的加速。

Answer 2

您可能只想在每个目录中扫描一次目录中的内容，因此处理顺序- 在访问其他目录之前或之后处理目录的内容可能比您是在执行深度优先还是广度优先更重要搜索。stat根据您的文件系统，与查看它们是文件还是目录相比，更快地处理文件节点也可能比处理它们更有效。所以我建议将预订深度优先搜索作为起点，因为它最容易实现并且最有可能具有良好的缓存/搜索性能。

总之 - 预订深度优先 - 在进入目录时，列出其内容，处理该目录中的所有文件，并保存子目录名称列表。然后依次进入每个子目录。只需将程序的调用堆栈用作堆栈，除非您知道您有非常深的目录结构。

Answer 3

广度优先会更好地工作是有道理的。当您进入根文件夹时，您会创建一个需要处理的项目列表。其中一些项目是文件，一些是目录。

如果您使用广度优先，您将处理目录中的文件并忘记它们，然后再转到其中一个子目录。

如果您使用深度优先，则需要不断增加文件列表，以便稍后在深入挖掘时处理。这将使用更多内存来维护您要处理的文件列表，可能会导致更多页面错误等......

另外，无论如何，您都需要浏览新项目列表，以确定哪些是您可以深入研究的目录。当您到达处理文件的地步时，您将需要再次浏览相同的列表（减去目录）。

Answer 4

使用 BFS 遍历目录结构（如 Igor 所述）。

当你到达一个目录时，启动一个线程来列出目录中的所有文件。

并在完成列出/遍历文件后终止线程。

因此，每个目录都会有单独的线程来列出文件。

例子：

root

  - d1
    - d1.1
    - d1.2
    - f1.1 ... f1.100

  - d2
    - d2.1
    - d2.2
    - d2.3
    - f2.1 ... f2.200

  - d3 
    ....

输出可能看起来像这样 ->

 got d1

   started thread to get files of d1

   got d2

   started thread to get files of d1

   done with files in d1

   got d3

   started thread to get files of d1

   got d1.1
   started thread to get files of d1.1

   got d1.2
   started thread to get files of d1.2

因此，当您返回遍历目录的深度时，获取文件的线程将（几乎）完成其工作。

希望这会有所帮助。

Answer 5

这将是 Windows 中最有效的（类 DirectoryTreeReader），它首先使用呼吸并存储每个目录。

static const uint64 DIRECTORY_INDICATOR = -1;//std::numeric_limits <uint64>::max();

class DirectoryContent {

public:
    DirectoryContent(const CString& path)
    : mIndex(-1) 
    {
        CFileFind finder;
        finder.FindFile(path + L"\\*.*");
        BOOL keepGoing = FALSE;
        do {
            keepGoing = finder.FindNextFileW();
            if (finder.IsDots()) {
                // Do nothing...
            } else if (finder.IsDirectory()) {
                mPaths.push_back(finder.GetFilePath());
                mSizes.push_back(DIRECTORY_INDICATOR);
            } else {
                mPaths.push_back(finder.GetFilePath());
                mSizes.push_back(finder.GetLength());
            }
        } while(keepGoing);
    }

    bool OutOfRange() const {
        return mIndex >= mPaths.size();
    }
    void Advance() {
        ++mIndex;
    }
    bool IsDirectory() const {
        return mSizes[mIndex] == DIRECTORY_INDICATOR;
    }
    const CString& GetPath() const {
        return mPaths[mIndex];
    }
    uint64 GetSize() const {
        return mSizes[mIndex];
    }

private:
    CStrings mPaths;
    std::vector <uint64> mSizes;
    size_t mIndex;
};

class DirectoryTreeReader{
    DirectoryTreeReader& operator=(const DirectoryTreeReaderRealtime& other) {};
    DirectoryTreeReader(const DirectoryTreeReaderRealtime& other) {};

public:
    DirectoryTreeReader(const CString& startPath)
    : mStartPath(startPath){
        Reset();
    }

    void Reset() {
        // Argh!, no clear() in std::stack
        while(!mDirectoryContents.empty()) {
            mDirectoryContents.pop(); 
        }
        mDirectoryContents.push( DirectoryContent(mStartPath) );
        Advance();
    }
    void Advance() {
        bool keepGoing = true;
        while(keepGoing) {
            if (mDirectoryContents.empty()){
                return;
            }
            mDirectoryContents.top().Advance();
            if (mDirectoryContents.top().OutOfRange()){
                mDirectoryContents.pop();
            } else if ( mDirectoryContents.top().IsDirectory() ){
                mDirectoryContents.push( DirectoryContent(mDirectoryContents.top().GetPath()) );
            } else {
                keepGoing = false;
            }
        }
    }
    bool OutOfRange() const {
        return mDirectoryContents.empty();
    }
    const CString& GetPath() const {
        return mDirectoryContents.top().GetPath();
    }
    uint64 GetSize() const {
        return mDirectoryContents.top().GetSize();
    }

private:
    const CString mStartPath;
    std::stack <DirectoryContent> mDirectoryContents;
};