Алгоритм обхода дерева для структур каталогов с большим количеством файлов

Это было бы наиболее эффективным в 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;
};

Структура каталогов Travse с использованием BFS (как упоминал Игорь).

Когда вы достигнете каталога, запустите поток, чтобы вывести список всех файлов в каталоге.

И убить поток, как только он завершает перечисление / просмотр файлов.

Итак, для каждого каталога будет отдельный поток для перечисления файлов.

ПРИМЕР:

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

Итак, когда вы придете назад, чтобы исследовать глубины каталога поток для получения файлов завершил бы (почти) свою работу.

Надеюсь, это поможет.

Поскольку у вас больше файлов, чем каталогов, не похоже, что вы имеете дело с очень глубоко вложенными каталогами, из-за которых DFS занимала бы больше памяти (и, следовательно, несколько больше времени), чем BFS. По сути, и BFS, и DFS делают одно и то же (т. Е. Посещают каждый узел графа), и поэтому в целом их скорости не должны отличаться на сколько-нибудь значительную величину.

Трудно сказать, почему именно ваша DFS медленнее, не фактически видя вашу реализацию. Вы уверены, что не посещаете одни и те же узлы более одного раза из-за ссылок / ярлыков в вашей файловой системе? Вы также, вероятно, получите значительное ускорение, если будете использовать DFS на основе явного стека вместо рекурсии.

Вероятно, вы хотите сканировать содержимое каталога только один раз для каждого каталога, поэтому порядок обработки - обрабатываете ли вы содержимое каталога до или после посещения других каталогов, вероятно, имеет большее значение чем выполняете ли вы поиск в глубину или в ширину. В зависимости от вашей файловой системы также может быть более эффективным обрабатывать файловые узлы раньше, чем позже, чем stat , чтобы увидеть, являются ли они файлами или каталогами. Поэтому я бы предложил в качестве отправной точки предварительный заказ поиска в глубину, как наиболее простой в реализации и, скорее всего, имеющий хорошую производительность кеширования / поиска.

В итоге - предварительный заказ в глубину - при входе в каталог, перечислить его содержимое, обработать любые файлы в этом каталоге и сохранить список имен дочерних каталогов. Затем войдите в каждый дочерний каталог по очереди. Просто используйте стек вызовов программы как стек, если вы не знаете, что у вас очень глубокая структура каталогов.