¿Cómo recuperar una lista de directorios RÁPIDAMENTE en Java?

Question

Supongamos un programa muy simple que enumera todos los subdirectorios de un directorio determinado. ¿Suena bastante simple? Excepto que la única forma de enumerar todos los subdirectorios en Java es usar FilenameFilter combinado con File.list().

Esto funciona para el caso trivial, pero cuando la carpeta tiene, por ejemplo, 150,000 archivos y 2 subcarpetas, es absurdo esperar allí 45 segundos recorriendo todos los archivos y probando file.isDirectory(). ¿Hay una mejor manera de enumerar los directorios secundarios?

---

PS. Lo sentimos, guarde las conferencias sobre tener demasiados archivos en el mismo directorio. Nuestro entorno en vivo tiene esto como parte del requisito.

Answer 1

Se podía entrar ilegalmente en él si el 150k todos los archivos (o un número significativo de ellos) tenía una convención de nomenclatura similar como:

*.jpg 
*Out.txt 

y sólo realmente crear objetos de archivo para los que no está seguro acerca de ser un carpeta.

Answer 2

Tal vez podría escribir un programa de búsqueda de directorio en C#/C/C++ y usar JNI para obtenerlo en Java. No sé si esto mejoraría el rendimiento o no.

Answer 3

En ese caso, puede intentar con alguna solución JNA, una extensión de directorio dependiente de la plataforma (FindFirst, FindNext en Windows) con la posibilidad de algún patrón de iteración. Además, Java 7 tendrá un soporte de sistema de archivos mucho mejor, vale la pena revisar las especificaciones (no recuerdo ninguna especificación).

Editar: Una idea: una opción es ocultar la lentitud de la lista de directorios de los ojos del usuario. En una aplicación del lado del cliente, puede usar un poco de animación mientras el listado está funcionando para distraer al usuario. En realidad, depende de qué más haga su aplicación junto a la lista.

Answer 4

En realidad, hay una razón por la que recibió las conferencias: es la respuesta correcta a su problema. Aquí está el fondo, por lo que quizás pueda hacer algunos cambios en su entorno en vivo.

Primero: los directorios se almacenan en el sistema de archivos; piense en ellos como archivos, porque eso es exactamente lo que son. Cuando itera por el directorio, debe leer esos bloques desde el disco. Cada entrada de directorio requerirá suficiente espacio para contener el nombre de archivo y los permisos, y la información sobre dónde se encuentra ese archivo en el disco.

Segundo: los directorios no se almacenan con ningún pedido interno (al menos, no en los sistemas de archivos donde he trabajado con archivos de directorio). Si tiene 150,000 entradas y 2 subdirectorios, esas 2 referencias de subdirectorios pueden estar en cualquier lugar dentro de los 150,000. Tienes que iterar para encontrarlos, no hay forma de evitar eso.

Digamos que no se puede evitar el directorio grande. Su única opción real es tratar de mantener los bloques que comprenden el archivo de directorio en la caché en memoria, de modo que no esté golpeando el disco cada vez que acceda a ellos. Puede lograr esto iterando regularmente sobre el directorio en una cadena de fondo, pero esto causará una carga excesiva en sus discos e interferirá con otros procesos. Alternativamente, puede escanear una vez y realizar un seguimiento de los resultados.

La alternativa es crear una estructura de directorios por niveles. Si observa sitios web comerciales, verá URL como /1/150/15023.html, con el objetivo de mantener pequeña la cantidad de archivos por directorio. Piense en ello como un índice de BTree en una base de datos.

Por supuesto, puede ocultar esa estructura: puede crear una capa de abstracción del sistema de archivos que tome los nombres de los archivos y genere automáticamente el árbol de directorios donde se encuentran esos nombres de archivo.

Answer 5

Bueno, o JNI, o, si usted dice que su implementación es constante, basta con ejecutar "dir" en Windows o "ls" en la nixes *, con banderas apropiadas para enumerar sólo directorios (Runtime.exec())

Answer 6

¿Conoces la lista finita de posibles nombres de subdirectorios? Si es así, use un ciclo sobre todos los nombres posibles y verifique la existencia del directorio. De lo contrario, no puede obtener SOLO nombres de directorio en la mayoría de los sistemas operativos subyacentes (por ejemplo, en Unix, el listado de directorios es simplemente leer los contenidos del archivo "directorio", por lo que no hay forma de encontrar archivos).

Sin embargo, en NIO.2 en Java7 (vea http://java.sun.com/developer/technicalArticles/javase/nio/#3), hay una manera de tener una lista de directorio de transmisión para que no obtenga una matriz completa de elementos de archivos que llenan su memoria/red.

Answer 7

No sé si la sobrecarga de los bombardeos a cabo a cmd.exe lo comería, pero una posibilidad sería algo como esto:

... 
Runtime r = Runtime.getRuntime(); 
Process p = r.exec("cmd.exe /k dir /s/b/ad C:\\folder"); 
BufferedReader br = new BufferedReader(new InputStreamReader(p.getInputStream())); 
for (;;) { 
    String d = br.readLine(); 
    if (d == null) 
     break; 
    System.out.println(d); 
} 
... 

• /s significa subdirectorios de búsqueda
• /anuncio significa solo directorios de devolución
• /b significa devolver la ruta completa de t que erradicar

Answer 8

si su sistema operativo es 'estable' darle una oportunidad a JNA:

• opendir/readdir en UNIX
• FindFirstFile y API relacionada en Windows
• Java7 con NIO2

estos son todos "streaming API". No te obligan a asignar una lista/matriz de 150k antes de comenzar la búsqueda. En mi humilde opinión, esta es una gran ventaja en su escenario.

Answer 9

Como ya se ha mencionado, esto es básicamente un problema de hardware. El acceso al disco siempre es lento, y la mayoría de los sistemas de archivos no están diseñados para manejar directorios con tantos archivos.

Si por algún motivo tiene que almacenar todos los archivos en el mismo directorio, creo que deberá mantener su propio caché. Esto podría hacerse usando una base de datos local como sqlite, HeidiSQL o HSQL. Si desea un rendimiento extremo, use un TreeSet java y almacénelo en la memoria caché. Esto significa, como mínimo, que tendrá que leer el directorio con menos frecuencia y posiblemente se haga en segundo plano. Podría reducir la necesidad de actualizar aún más la lista utilizando la API de notificaciones de actualización de archivos nativos de su sistema (inotify en Linux) para suscribirse a los cambios en el directorio.

Esto no parece posible para usted, pero una vez resolví un problema similar al "hash" los archivos en subdirectorios. En mi caso, el desafío fue almacenar un par de millones de imágenes con identificadores numéricos.Construí la estructura de directorios de la siguiente manera:

images/[id - (id % 1000000)]/[id - (id % 1000)]/[id].jpg 

Esto ha funcionado bien para nosotros, y es la solución que yo recomendaría. Podría hacer algo similar a los nombres de archivo alfanuméricos simplemente tomando las dos primeras letras del nombre del archivo, y luego las dos letras siguientes. He hecho esto también una vez, y también hizo el trabajo.

Answer 10

También hay un escaneo recursivo paralelo en http://blogs.oracle.com/adventures/entry/fast_directory_scanning. Esencialmente, los hermanos se procesan en paralelo. También hay pruebas de rendimiento alentadoras.

Answer 11

Aquí hay una solución fuera de la pared, y sin ninguna prueba en absoluto. También depende de tener un sistema de archivos que admita enlaces simbólicos. Esta no es una solución Java. Sospecho que su problema está relacionado con el sistema de archivos/sistema operativo y no con Java.

¿Es posible crear una estructura de directorios paralelos, con subdirectorios basados ​​en letras iniciales de los nombres de los archivos, y luego vincularlos simbólicamente a los archivos reales? Una ilustración

/symlinks/a/b/cde 

vincularía a

/realfiles/abcde 

(donde/realfiles es donde sus archivos residen 150.000)

Habría que crear y mantener esta estructura de directorios, y yo don' t tiene suficiente información para determinar si eso es práctico. Pero lo anterior crearía un índice rápido (er) en su directorio no jerárquico (y lento).

Answer 12

El problema clave podría ser la función File.isDirectory() llamada en un bucle.

File.isDirectory() puede ser extremadamente lento. Vi que NFS tarda 10 segundos en procesar el directorio de 200 archivos.

Si puede evitar todas las llamadas a File.isDirectory() (por ejemplo, prueba de extensión, sin extensión == directorio), puede mejorar el rendimiento drásticamente.

De lo contrario, sugeriría hacer JNA/JNI/escritura de un guión nativo que lo hace por usted.

La biblioteca jCifs permite manipular recursos compartidos de red de Windows de manera más eficiente. No conozco una biblioteca que pueda hacer esto para otros sistemas de archivos de red.

Answer 13

me encontré pregunta similar al depurar el rendimiento en una aplicación Java enumerar un montón de archivos. Se está utilizando el enfoque de edad

for (File f : new File("C:\\").listFiles()) { 
    if (f.isDirectory()) { 
     continue; 
    }   
} 

Y parece que cada f.isDirectory() es la llamada en FileSsystem nativa que, al menos en NTFS, es muy lento. Java7 NIO tiene API adicional, pero no todos los métodos son buenos allí. Voy a proporcionar JMH resultado del benchmark aquí

Benchmark     Mode Cnt Score Error Units 
MyBenchmark.dir_listFiles avgt 5 0.437 ? 0.064 s/op 
MyBenchmark.path_find  avgt 5 0.046 ? 0.001 s/op 
MyBenchmark.path_walkTree avgt 5 1.702 ? 0.047 s/op 

Número provienen de ejecución de este código:

java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1 

static final String testDir = "C:/Sdk/Ide/NetBeans/src/dev/src/"; 
static final int nCycles = 50; 

public static class Counter { 
    int countOfFiles; 
    int countOfFolders; 
} 

@Benchmark 
public List<File> dir_listFiles() { 
    List<File> files = new ArrayList<>(1000); 

    for(int i = 0; i < nCycles; i++) { 
     File dir = new File(testDir); 

     files.clear(); 
     for (File f : dir.listFiles()) { 
      if (f.isDirectory()) { 
       continue; 
      } 
      files.add(f); 
     } 
    } 
    return files; 
} 

@Benchmark 
public List<Path> path_walkTree() throws Exception { 
    final List<Path> files = new ArrayList<>(1000); 

    for(int i = 0; i < nCycles; i++) { 
     Path dir = Paths.get(testDir); 

     files.clear(); 
     Files.walkFileTree(dir, new SimpleFileVisitor<Path>() { 
      @Override 
      public FileVisitResult visitFile(Path path, BasicFileAttributes arg1) throws IOException { 
       files.add(path); 
       return FileVisitResult.CONTINUE; 
      } 

      @Override 
      public FileVisitResult preVisitDirectory(Path path, BasicFileAttributes arg1) 
        throws IOException { 
       return path == dir ? FileVisitResult.CONTINUE : FileVisitResult.SKIP_SUBTREE; 
      } 
     }); 
    } 

    return files; 
} 

@Benchmark 
public List<Path> path_find() throws Exception { 
    final List<Path> files = new ArrayList<>(1000); 

    for(int i = 0; i < nCycles; i++) { 
     Path dir = Paths.get(testDir); 

     files.clear(); 
     files.addAll(Files.find(dir, 1, (path, attrs) 
       -> true /*!attrs.isDirectory()*/).collect(Collectors.toList())); 
    } 

    return files; 
}