Algoritmo di attraversamento dell'albero per strutture di directory con molti file

Question

Quando si attraversa in modo ricorsivo attraverso una struttura di directory, qual è l'algoritmo più efficiente da utilizzare se si dispone di più file rispetto alle directory? Ho notato che quando si utilizza deep-first traversal, sembra che ci voglia più tempo quando ci sono molti file in una determinata directory. In questo caso, la traversata in ampiezza funziona in modo più efficiente? Non ho modo di tracciare i due algoritmi al momento, quindi le tue opinioni sono benvenute.

MODIFICA: in risposta al commento di alphazero, sto usando PHP su una macchina Linux.

Answer 1

Ha senso che l'ampiezza funzionerebbe meglio. Quando si inserisce la cartella principale, si crea un elenco di elementi che è necessario trattare. Alcuni di questi elementi sono file e alcuni sono directory.

Se si utilizza l'ampiezza, si gestiscono i file nella directory e si dimenticano di essi prima di passare a una delle directory secondarie.

Se si utilizza depth-first, è necessario continuare a crescere un elenco di file da trattare in seguito mentre si scava più in profondità. Questo userebbe più memoria per mantenere il tuo elenco di file da trattare, causando probabilmente più errori di pagina, ecc ...

Inoltre, avresti bisogno di passare attraverso l'elenco di nuovi elementi comunque per capire quali sono directory su cui è possibile eseguire il drill. Avresti bisogno di passare attraverso quella stessa lista (meno le directory) di nuovo quando hai raggiunto il punto di trattare con i file.

Answer 2

Struttura della cartella Travse utilizzando BFS (come indicato da Igor).

Quando si raggiunge una directory, avviare un thread per elencare tutti i file nella directory.

E interrompere il thread una volta terminato l'elenco/travse dei file.

Quindi, ci sarà un thread separato per ogni directory per elencare i file.

ESEMPIO:

root 

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

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

    - d3 
    .... 

USCITA potrebbe assomigliare a questo ->

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 

Quindi per il momento si torna a travse profondità di una directory il filo per ottenere i file sarebbe aver finito (quasi) il suo lavoro.

Spero che questo sia utile.

Answer 3

Questo sarebbe il più efficace in Windows (class DirectoryTreeReader), utilizza prima breath e memorizza tutte le directory.

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

Dal momento che si dispone di più file di directory, non apparire come se avete a che fare con le directory molto profondamente nidificate che renderebbero DFS di prendere più memoria (e quindi un po 'più di tempo) di BFS. Essenzialmente, BFS e DFS fanno entrambe la stessa cosa (ad esempio visitano ogni nodo del grafico) e quindi in generale le loro velocità non dovrebbero differire di una quantità significativa.

È difficile dire perché esattamente il DFS è più lento senza effettivamente vedere l'implementazione. Sei sicuro di non visitare gli stessi nodi più di una volta a causa di link/scorciatoie nel tuo filesystem?Probabilmente otterrai anche un notevole aumento della velocità se utilizzi un DFS basato su stack esplicito piuttosto che una ricorsione.

Answer 5

Probabilmente si desidera solo eseguire la scansione del contenuto in una directory una volta per directory, quindi processing order - se si elabora il contenuto di una directory prima o dopo aver visitato altre directory probabilmente importa più o meno se si sta eseguendo una profondità o ricerca in ampiezza. A seconda del tuo file system, potrebbe anche essere più efficiente elaborare i nodi dei file prima e dopo il stat per vedere se sono file o directory. Quindi suggerirei una ricerca in profondità pre-ordine come punto di partenza, la più semplice da implementare e molto probabilmente con buone prestazioni di cache/ricerca.

In sintesi - pre-ordine depth-first - All'ingresso in una directory, elencarne il contenuto, elaborare tutti i file in quella directory e salvare un elenco di nomi di directory figlio. Quindi inserisci a turno ciascuna directory secondaria. Usa semplicemente lo stack di chiamata del programma come stack, a meno che tu non sappia che hai una struttura di directory molto profonda.