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

Question

При рекурсивном обходе структуры каталогов, какой алгоритм наиболее эффективен, если у вас больше файлов, чем каталогов? Я заметил, что при использовании обхода в глубину, кажется, это занимает больше времени, когда в данном каталоге много файлов. Работает ли обход в ширину более эффективно в этом случае? У меня нет способа профилировать эти два алгоритма на данный момент, поэтому ваши идеи очень приветствуются.

РЕДАКТИРОВАТЬ: В ответ на комментарий alphazero я использую PHP на машине Linux.

Answer 1

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

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

Answer 2

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

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

Answer 3

Имеет смысл, что в ширину будет работать лучше. Когда вы входите в корневую папку, вы создаете список элементов, с которыми вам нужно иметь дело. Некоторые из этих элементов являются файлами, а некоторые каталогами.

Если вы используете ширину в первую очередь, вы будете иметь дело с файлами в каталоге и забудете о них, прежде чем перейти к одному из дочерних каталогов.

Если вы используете глубину в первую очередь, вам нужно продолжать увеличивать список файлов, с которыми вы будете иметь дело позже, когда будете углубляться в детали. Это использовало бы больше памяти для ведения списка файлов, с которыми можно иметь дело, возможно, вызывая больше сбоев страниц и т. Д ...

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

Answer 4

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

Answer 5

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

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

И уничтожить поток, как только он закончит перечислять / перемещать файлы.

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

Пример:

root

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

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

  - d3 
    ....

OUTPUT может выглядеть так ->

 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

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

Надеюсь, это полезно.