많은 파일이있는 디렉토리 구조에 대한 트리 순회 알고리즘

Question

디렉토리 구조를 재귀 적으로 탐색 할 때 디렉토리보다 많은 파일이있는 경우 가장 효율적인 알고리즘은 무엇입니까? 깊이 우선 탐색을 사용할 때 주어진 디렉토리에 많은 파일이있을 때 더 오래 걸리는 것처럼 보입니다. 이 경우에는 너비 우선 탐색이 더 효율적입니까? 나는 당신의 통찰력을 대단히 환영 할 수 있도록이 두 가지 알고리즘을 프로파일 링 할 방법이 없습니다.

EDIT : alphazero 님의 의견에 대한 답변으로 Linux 컴퓨터에서 PHP를 사용하고 있습니다.

Answer 1

폭 우선이 더 효과적 일 것입니다. 루트 폴더를 입력 할 때 처리해야 할 항목 목록을 만듭니다. 이러한 항목 중 일부는 파일이고 일부는 디렉토리입니다.

너비를 우선으로 사용하는 경우 하위 디렉토리 중 하나로 이동하기 전에 디렉토리의 파일을 처리하고 잊어 버릴 수 있습니다.

깊이 우선을 사용하는 경우 나중에 드릴 다운 할 때 나중에 처리 할 파일 목록을 늘려야합니다. 이렇게하면 더 많은 메모리를 사용하여 처리 할 파일 목록을 유지 관리하므로 페이지 폴트 등이 발생할 수 있습니다.

더하여, 어떤 항목이 있는지 파악하기 위해 새 항목 목록을 검토해야합니다 디렉토리를 드릴 할 수 있습니다. 파일을 처리 할 때 동일한 목록 (디렉토리 제외)을 다시 거쳐야합니다.

Answer 2

BFS를 사용하는 Travse 디렉토리 구조 (Igor 언급).

디렉토리에 도달하면 디렉토리의 모든 파일을 나열하는 스레드를 시작하십시오.

그리고 목록 파일/travseing 파일을 완료하면 스레드를 종료하십시오.

그래서 각 디렉토리에 파일을 나열하는 별도의 스레드가 있습니다.

예 :

root 

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

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

    - d3 
    .... 

OUTPUT은 다음과 같이 나타납니다 ->

디렉토리 파일을 얻을 수있는 스레드의 깊이를 travse하는 당신이 돌아올 때까지는 그래서

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 3

이것은 Windows (class DirectoryTreeReader)에서 가장 효과적이며 숨을 먼저 사용하고 모든 디렉토리를 저장합니다. 당신이 디렉토리보다 더 많은 파일을 가지고 있기 때문에 당신은 DFS는 BFS보다 더 많은 메모리 (따라서 다소 시간이) 걸릴 수 있도록 것입니다 매우 깊게 중첩 된 디렉토리를 처리하는 것처럼

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 4

, 그것은 표시되지 않습니다. 본질적으로 BFS와 DFS는 모두 동일한 작업을 수행하므로 그래프의 모든 노드를 방문하므로 일반적으로 속도가 크게 달라지지 않아야합니다.

구현을 실제로 보지 않고도 DFS가 왜 더 느린지 말할 수 없습니다. 파일 시스템의 링크/바로 가기 때문에 두 번 이상 같은 노드를 방문하지 않습니까?재귀가 아닌 명시 적 스택 기반 DFS를 사용하면 상당한 속도 향상을 얻을 수 있습니다.

Answer 5

디렉토리마다 내용을 한 번만 검색하면되므로 processing order - 다른 디렉토리를 방문하기 전후에 디렉토리의 내용을 처리할지 여부는 깊이 우선 또는 너비 우선 검색. 파일 시스템에 따라 파일 노드인지 여부를 알아보기 위해 파일 노드를 stat보다 빨리 처리하는 것이 아니라 더 빨리 처리하는 것이 더 효율적일 수 있습니다. 따라서 사전 주문 깊이 우선 검색을 시작 지점으로 제안하고, 구현하기가 가장 쉽고 캐시/검색 성능이 가장 좋을 것입니다.

요약 - 선주문 깊이 우선 - 디렉토리에 들어가면 해당 내용을 나열하고 해당 디렉토리의 파일을 처리하며 하위 디렉토리 이름 목록을 저장합니다. 그런 다음 각 하위 디렉토리를 차례로 입력하십시오. 방대한 디렉토리 구조를 알고있는 경우를 제외하고는 프로그램의 호출 스택을 스택으로 사용하십시오.