Thuật toán truyền tải cây cho cấu trúc thư mục với nhiều tệp

Question

Khi đệ quy truyền qua cấu trúc thư mục, thuật toán hiệu quả nhất để sử dụng nếu bạn có nhiều tệp hơn thư mục là gì? Tôi nhận thấy rằng khi sử dụng traversal độ sâu đầu tiên, có vẻ như mất nhiều thời gian hơn khi có nhiều tệp trong một thư mục nhất định. Bề ngang đầu tiên có hoạt động hiệu quả hơn trong trường hợp này không? Tôi không có cách nào để lập hồ sơ hai thuật toán vào lúc này để thông tin chi tiết của bạn được chào đón rất nhiều.

EDIT: Để trả lời nhận xét của alphazero, tôi đang sử dụng PHP trên máy Linux.

Answer 1

Điều đó có ý nghĩa rằng bề rộng đầu tiên sẽ hoạt động tốt hơn. Khi bạn nhập thư mục gốc của mình, bạn tạo danh sách các mục bạn cần xử lý. Một số mục đó là các tệp và một số là các thư mục.

Nếu bạn sử dụng chiều rộng đầu tiên, bạn sẽ xử lý các tệp trong thư mục và quên chúng trước khi chuyển sang một trong các thư mục con.

Nếu bạn sử dụng độ sâu đầu tiên, bạn cần tiếp tục phát triển danh sách tệp để xử lý sau khi bạn đi sâu hơn. Điều này sẽ sử dụng nhiều bộ nhớ hơn để duy trì danh sách các tệp của bạn để xử lý, có thể gây ra nhiều lỗi trang hơn, v.v ...

Ngoài ra, bạn cần xem qua danh sách các mục mới để tìm ra mục nào các thư mục mà bạn có thể đi sâu vào. Bạn sẽ cần phải đi qua cùng một danh sách (trừ các thư mục) một lần nữa khi bạn đã nhận được đến điểm đối phó với các tập tin.

Answer 2

Cấu trúc thư mục chuyến đi bằng BFS (như Igor đã đề cập).

Khi bạn đến thư mục, hãy bắt đầu một chuỗi để liệt kê tất cả các tệp trong thư mục.

Và xóa chuỗi sau khi hoàn tất việc liệt kê/truy xuất tệp.

Vì vậy, sẽ có chuỗi riêng biệt cho từng thư mục để liệt kê tệp.

VÍ DỤ:

root 

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

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

    - d3 
    .... 

OUTPUT có thể trông như thế này ->

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 

Vì vậy, bằng thời gian bạn quay trở lại travse chiều sâu của một thư mục thread để có được file sẽ đã hoàn thành (gần như) công việc của mình.

Hy vọng điều này hữu ích.

Answer 3

Điều này sẽ hiệu quả nhất trong Windows (lớp DirectoryTreeReader), nó sử dụng hơi thở đầu tiên và lưu trữ mọi thư mục.

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

Vì bạn có nhiều tệp hơn thư mục, nó không xuất hiện như thể bạn đang xử lý các thư mục lồng nhau rất sâu khiến DFS mất nhiều bộ nhớ hơn (và do đó phần lớn thời gian) hơn BFS. Về cơ bản, BFS và DFS đều làm điều tương tự (ví dụ: truy cập mọi nút của biểu đồ), và do đó nói chung tốc độ của chúng không được khác nhau bởi bất kỳ số lượng đáng kể nào.

Thật khó để nói lý do chính xác DFS của bạn chậm hơn mà không thực sự thấy triển khai của bạn. Bạn có chắc là bạn không truy cập vào cùng một nút nhiều lần do các liên kết/lối tắt trong hệ thống tệp của bạn không?Bạn cũng sẽ có thể nhận được một tốc độ đáng kể nếu bạn sử dụng một DFS rõ ràng dựa trên DFS chứ không phải đệ quy.

Answer 5

Bạn có thể chỉ muốn quét nội dung trong thư mục một lần cho mỗi thư mục, do đó, bạn có thể xử lý nội dung của thư mục trước hoặc sau khi truy cập các thư mục khác có thể quan trọng hơn bạn có đang làm sâu hay không tìm kiếm theo chiều rộng. Tùy thuộc vào hệ thống tập tin của bạn, nó cũng có thể có hiệu quả hơn để xử lý các nút tập tin sớm hơn là sau khi stat ing chúng để xem nếu họ là các tập tin hoặc thư mục. Vì vậy, tôi muốn đề xuất tìm kiếm đầu tiên theo chiều sâu đầu tiên là điểm bắt đầu, dễ nhất để triển khai và có nhiều khả năng có hiệu suất bộ nhớ cache/tìm kiếm tốt nhất.

Tóm tắt - đặt trước độ sâu đầu tiên - Khi nhập một thư mục, hãy liệt kê nội dung của nó, xử lý bất kỳ tệp nào trong thư mục đó và lưu danh sách tên thư mục con. Sau đó nhập từng thư mục con. Chỉ cần sử dụng ngăn xếp cuộc gọi của chương trình như ngăn xếp, trừ khi bạn biết bạn có cấu trúc thư mục sâu bao la.