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

Question

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

编辑：针对 alphazero 的评论，我正在 Linux 机器上使用 PHP。

- oninea

---

为什么你不能对这两个算法进行性能分析？ - Zoidberg

给Zoidberg：实际上，我不知道如何正确地做。我刚开始重新学习开发，并且遇到了当我还在大学时遇到的相同问题。但这一次，我想更好地理解事情。你有什么好的方法来有效地测试吗？ - oninea

除非您指定（a）语言/操作系统，（b）您正在对文件执行什么操作，否则您将无法获得任何有意义的答案。此外，“似乎需要更长时间”听起来并不准确。从基础知识开始：在开始之前获取系统时间，并在完成后测量增量，以便您/我们知道是“似乎”还是“确实”。 - alphazero

抱歉表述不够清晰。我无法像你期望的那样具体，因为我不知道如何正确地测试这个案例。我之所以提出这个问题，正是为了解决这个问题。 - oninea

@oninea 在你的代码中添加一个计时变量，看看遍历一个目录需要多长时间。 - user151841

Answer 1

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

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

- MAK

Answer 2

你可能只想每个目录扫描一次其内容，因此处理顺序（在访问其他目录之前或之后处理目录的内容）比深度优先或广度优先搜索更重要。根据你的文件系统，更高效的方法可能是尽早处理文件节点而不是稍后stat查看它们是文件还是目录。因此，我建议从先序深度优先搜索开始作为起点，因为它最容易实现，并且最有可能具有良好的缓存/搜索性能。

总之 - 先序深度优先 - 进入目录时，列出其内容，处理该目录中的任何文件，并保存子目录名称列表。然后依次进入每个子目录。除非你知道自己有非常深的目录结构，否则只需使用程序的调用堆栈作为堆栈即可。

- Pete Kirkham

Answer 3

使用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

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

希望这对你有所帮助。

- Pratik Deoghare

Answer 4

当你进入根目录时，创建一个需要处理的项目列表。其中一些项目是文件，一些是目录。广度优先算法更好理解。如果使用广度优先算法，您将处理目录中的文件，并在转移到子目录之前忘记它们。如果使用深度优先算法，您需要在向下钻取时不断扩展待处理文件列表。为维护待处理文件列表而使用更多内存，可能会导致更多的页面错误等问题。此外，您仍然需要浏览新项目列表以确定哪些是可进入的目录。当到达处理文件点时，您需要再次浏览相同列表（减去目录）。

- Igor Serebryany

---

你的“广度优先”搜索算法描述应该翻译成“先序深度优先搜索”。 - Pete Kirkham

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;
};

- Viktor Sehr