15

ディレクトリ構造を再帰的にトラバースするとき、ディレクトリよりも多くのファイルがある場合に使用する最も効率的なアルゴリズムは何ですか? 深さ優先トラバーサルを使用すると、特定のディレクトリに多くのファイルがあると時間がかかるように見えることに気付きました。この場合、幅優先トラバーサルはより効率的に機能しますか? 現時点では 2 つのアルゴリズムの概要を説明する方法がないため、ご意見をお待ちしております。

編集: alphazero のコメントに応えて、私は Linux マシンで PHP を使用しています。

4

5 に答える 5

4

ディレクトリよりも多くのファイルがあるため、DFS が BFS よりも多くのメモリ (したがって、多少時間がかかる) を必要とする非常に深くネストされたディレクトリを扱っているようには見えません。基本的に、BFS と DFS はどちらも同じことを行います (つまり、グラフのすべてのノードにアクセスします)。

実際に実装を見ずに、DFS が遅い理由を正確に言うのは困難です。ファイルシステムのリンク/ショートカットが原因で、同じノードに複数回アクセスしていませんか? また、再帰ではなく、明示的なスタック ベースの DFS を使用すると、おそらく大幅な速度向上が得られます。

于 2009-12-17T14:13:21.753 に答える
3

ディレクトリ内のコンテンツをディレクトリごとに1回だけスキャンする必要があるため、処理順序-他のディレクトリにアクセスする前または後にディレクトリのコンテンツを処理するかどうかは、深さ優先または幅優先のどちらを実行するかよりも重要です。探す。statファイルシステムによっては、ファイルノードがファイルであるかディレクトリであるかを確認するよりも、ファイルノードを後で処理するよりも早く処理する方が効率的な場合もあります。したがって、実装が最も簡単で、キャッシュ/シークのパフォーマンスが高い可能性が最も高い、事前注文の深さ優先探索を開始点として提案します。

要約すると、深さ優先の事前注文-ディレクトリに入ると、その内容をリストし、そのディレクトリ内のファイルを処理し、子ディレクトリ名のリストを保存します。次に、各子ディレクトリを順番に入力します。非常に深いディレクトリ構造があることがわかっている場合を除いて、プログラムの呼び出しスタックをスタックとして使用するだけです。

于 2009-12-18T10:09:28.270 に答える
2

BFS を使用した Travse ディレクトリ構造 (Igor が述べたように)。

ディレクトリに到達したら、スレッドを開始して、ディレクトリ内のすべてのファイルを一覧表示します。

そして、ファイルの一覧表示/走査が終了したら、スレッドを強制終了します。

そのため、ファイルを一覧表示するために、ディレクトリごとに個別のスレッドがあります。

例：

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

したがって、ディレクトリの深さを探索するために戻ってくるまでに、ファイルを取得するためのスレッドはその仕事を (ほぼ) 終了しています。

これが役に立てば幸いです。

于 2009-12-17T12:59:09.463 に答える
1

これは、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;
};
于 2009-12-17T13:05:32.180 に答える