Algoritmo transversal de árbol para estructuras de directorios con muchos archivos

Question

Al recorrer recursivamente a través de una estructura de directorios, ¿cuál es el algoritmo más eficiente para usar si tiene más archivos que directorios? Observé que cuando se utiliza el recorrido en profundidad primero, parece tomar más tiempo cuando hay muchos archivos en un directorio determinado. ¿El cruce transversal en anchura funciona de manera más eficiente en este caso? No tengo manera de perfilar los dos algoritmos en este momento, por lo que tus ideas son bienvenidas.

EDIT: En respuesta al comentario de alphazero, estoy usando PHP en una máquina Linux.

Answer 1

Tiene sentido que la amplitud de funcionamiento funcione mejor. Cuando ingresa su carpeta raíz, crea una lista de elementos con los que debe lidiar. Algunos de esos elementos son archivos y algunos son directorios.

Si usa el ancho primero, trataría con los archivos en el directorio y los olvidaría antes de pasar a uno de los directorios secundarios.

Si utiliza la profundidad primero, necesita seguir creciendo una lista de archivos para tratar más adelante a medida que profundiza más abajo. Esto usaría más memoria para mantener su lista de archivos a tratar, posiblemente causando más fallas de página, etc. ...

Además, necesitaría revisar la lista de nuevos elementos de todos modos para descubrir cuáles son directorios en los que puedes profundizar Tendría que pasar por la misma lista (menos los directorios) nuevamente cuando haya llegado al punto de tratar con los archivos.

Answer 2

Estructura de directorios Travse utilizando BFS (como se mencionó Igor).

Cuando llegue a un directorio, inicie un hilo para enumerar todos los archivos en el directorio.

Y elimine el hilo una vez que termine de listar/recorrer archivos.

Por lo tanto, habrá un hilo separado para cada directorio para listar los archivos.

Ejemplo:

root 

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

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

    - d3 
    .... 

SALIDA podría tener este aspecto ->

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 

Así que para cuando vuelvas a travse las profundidades de un directorio el hilo para obtener archivos haría haber terminado (casi) su trabajo.

Espero que esto sea útil.

Answer 3

Esto sería lo más eficaz en Windows (clase DirectoryTreeReader), utiliza primero el aliento y almacena todos los directorios.

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

Puesto que usted tiene más archivos de los directorios, no aparecer como si se trata de directorios anidados muy profundamente que harían DFS para tener más memoria (y por lo tanto un poco más de tiempo) que BFS. Esencialmente, BFS y DFS hacen lo mismo (es decir, visitan todos los nodos del gráfico), por lo que, en general, sus velocidades no deberían diferir en ninguna cantidad significativa.

Es difícil decir por qué exactamente su DFS es más lento sin ver su implementación. ¿Estás seguro de que no estás visitando los mismos nodos más de una vez debido a enlaces/accesos directos en tu sistema de archivos?Probablemente también obtendrá una aceleración significativa si usa un DFS basado en pila explícito en lugar de la recursión.

Answer 5

Probablemente solo desee escanear los contenidos en un directorio una vez por directorio, entonces processing order - si procesa los contenidos de un directorio antes o después de visitar otros directorios probablemente importe más que si está haciendo primero o no búsqueda de amplitud Dependiendo de su sistema de archivos, también puede ser más eficiente procesar nodos de archivos más pronto que más tarde que stat para ver si son archivos o directorios. Por lo tanto, sugiero que se realice una búsqueda previa de primer orden como punto de partida, que sea más fácil de implementar y que tenga un buen rendimiento de caché/búsqueda.

En resumen - preordenar con profundidad primero - Al ingresar a un directorio, liste su contenido, procese cualquier archivo en ese directorio y guarde una lista de nombres de directorio secundarios. Luego ingrese cada directorio secundario a su vez. Solo use la pila de llamadas del programa como pila, a menos que sepa que tiene estructuras de directorios muy profundas.