Come recuperare un elenco di directory velocemente in Java?

Supponiamo un programma molto semplice che elenca tutte le sottodirectory di una determinata directory. Sembra abbastanza semplice? Tranne l’unico modo per elencare tutte le sottodirectory in Java è usare FilenameFilter in combinazione con File.list () .

Questo funziona per il caso banale, ma quando la cartella dice 150.000 file e 2 sottocartelle, è sciocco in attesa per 45 secondi di iterazione di tutti i file e test per file.isDirectory (). C’è un modo migliore per elencare sottodirectory?


PS. Siamo spiacenti, si prega di salvare le lezioni su avere troppi file nella stessa directory. Il nostro ambiente live ha questo come parte del requisito.

Come è già stato detto, questo è fondamentalmente un problema hardware. L’accesso al disco è sempre lento e la maggior parte dei file system non sono progettati per gestire le directory con così tanti file.

Se per qualche ragione devi memorizzare tutti i file nella stessa directory, penso che dovrai mantenere la tua cache. Questo potrebbe essere fatto usando un database locale come sqlite, HeidiSQL o HSQL. Se si desidera prestazioni estreme, utilizzare un TreeSet java e salvarlo nella memoria. Ciò significa almeno che dovrai leggere la directory meno spesso e che potrebbe essere fatto in background. È ansible ridurre la necessità di aggiornare ulteriormente l’elenco utilizzando l’API di notifica dell’aggiornamento file nativo dei sistemi (inotify on linux) per sottoscrivere le modifiche alla directory.

Questo non sembra essere ansible per te, ma una volta ho risolto un problema simile “eseguendo l’hash” dei file in sottodirectory. Nel mio caso, la sfida consisteva nel memorizzare un paio di milioni di immagini con ID numerici. Ho costruito la struttura delle directory come segue:

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

Questo ha funzionato bene per noi, ed è la soluzione che raccomanderei. Si potrebbe fare qualcosa di simile ai nomi alfanumerici semplicemente prendendo le prime due lettere del nome del file, e quindi le successive due lettere. Ho fatto anche questo una volta, e ha fatto anche il lavoro.

Conoscete l’elenco finito di possibili nomi di sottodirectory? In tal caso, utilizzare un ciclo su tutti i possibili nomi e verificare l’esistenza della directory.

Altrimenti, non è ansible ottenere SOLO nomi di directory nella maggior parte dei sistemi operativi sottostanti (ad esempio in Unix, l’elenco delle directory sta semplicemente leggendo il contenuto del file “directory”, quindi non c’è modo di trovare rapidamente “solo directory” senza elencare tutti i file).

Tuttavia, in NIO.2 in Java7 (vedi http://java.sun.com/developer/technicalArticles/javase/nio/#3 ), c’è un modo per avere un elenco di directory di streaming in modo da non ottenere un array completo di elementi di file che ingombrano la tua memoria / rete.

In realtà c’è una ragione per cui hai tenuto le lezioni: è la risposta corretta al tuo problema. Ecco lo sfondo, in modo che forse tu possa apportare alcune modifiche al tuo ambiente live.

Primo: le directory sono memorizzate sul filesystem; pensali come file, perché è esattamente quello che sono. Quando si scorre la directory, è necessario leggere quei blocchi dal disco. Ogni voce di directory richiederà spazio sufficiente per contenere il nome file, le autorizzazioni e le informazioni su dove quel file viene trovato su disco.

Secondo: le directory non sono archiviate con alcun ordinamento interno (almeno, non nei filesystem in cui ho lavorato con i file di directory). Se si hanno 150.000 voci e 2 sottodirectory, questi 2 riferimenti di sottodirectory potrebbero essere ovunque all’interno dei 150.000. Devi iterare per trovarli, non c’è modo di aggirarli.

Quindi, diciamo che non puoi evitare la grande directory. La tua unica vera opzione è cercare di mantenere i blocchi che comprendono il file di directory nella cache in memoria, in modo da non colpire il disco ogni volta che li accedi. È ansible ottenere questo aggiornando regolarmente la directory in un thread in background, ma questo causerà un carico eccessivo sui dischi e interferirà con altri processi. In alternativa, è ansible eseguire la scansione una volta e tenere traccia dei risultati.

L’alternativa è creare una struttura di directory a livelli. Se guardi i siti web commerciali, vedrai URL come /1/150/15023.html – questo serve a mantenere basso il numero di file per directory. Pensalo come un indice BTree in un database.

Ovviamente, puoi hide quella struttura: puoi creare un livello di astrazione del filesystem che prende i nomi dei file e genera automaticamente l’albero delle directory in cui è ansible trovare quei nomi di file.

Non so se il sovraccarico del bombardamento verso cmd.exe lo mangerebbe, ma una possibilità sarebbe una cosa del genere:

 ... 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 indica sottodirectory di ricerca
  • / annuncio significa solo restituire directory
  • / b significa che restituisce il percorso completo dalla radice

Puoi hackerarlo se i file 150k tutti (o un numero significativo di essi) hanno una convenzione di denominazione simile come:

 *.jpg *Out.txt 

e solo in realtà creano oggetti file per quelli che non si sono sicuri di essere una cartella.

Il problema chiave potrebbe essere la funzione File.isDirectory () chiamata in un ciclo.

File.isDirectory () può essere estremamente lento. Ho visto NFS impiegare 10 secondi per elaborare 200 directory di file.

Se è ansible evitare in ogni caso le chiamate a File.isDirectory () (ad esempio, prova per l’estensione, nessuna estensione == directory), è ansible migliorare drasticamente le prestazioni.

Altrimenti suggerirei di fare JNA / JNI / scrivere uno script nativo che faccia questo per te.

La libreria jCifs ti consente di manipolare le condivisioni di rete di Windows in modo più efficiente. Non sono a conoscenza di una libreria che farebbe questo per altri file system di rete.

se il tuo sistema operativo è “stabile” dai una prova a JNA :

  • opendir / readdir su UNIX
  • FindFirstFile e API correlata su Windows
  • Java7 con NIO2

queste sono tutte “API di streaming”. Non ti obbligano ad allocare una lista / array di 150k prima di iniziare la ricerca. IMHO questo è un grande vantaggio nel tuo scenario.

Ecco una soluzione off-the wall, e priva di qualsiasi test. Dipende anche dall’avere un filesystem che supporta collegamenti simbolici. Questa non è una soluzione Java. Sospetto che il tuo problema sia relativo al filesystem / al sistema operativo e non a Java.

È ansible creare una struttura di directory parallela, con sottodirectory basate sulle lettere iniziali dei nomi di file e quindi colbind simbolicamente ai file reali? Un’illustrazione

 /symlinks/a/b/cde 

collegherebbe a

 /realfiles/abcde 

(dove / realfiles è dove risiedono i 150.000 file)

Dovresti creare e mantenere questa struttura di directory, e non ho abbastanza informazioni per determinare se è pratico. Ma quanto sopra creerebbe un indice veloce (er) nella tua directory non gerarchica (e lenta).

c’è anche una scansione parallela ricorsiva su http://blogs.oracle.com/adventures/entry/fast_directory_scanning . In sostanza i fratelli vengono elaborati in parallelo. Ci sono anche dei test di prestazione incoraggianti.

Mi sono imbattuto in una domanda simile quando eseguivo il debug delle prestazioni in un’applicazione Java che enumerava molti file. Sta usando un vecchio approccio

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

E sembra che ogni f.isDirectory () sia la chiamata in FileSsystem nativo che, almeno su NTFS, è molto lento. Java7 NIO ha API aggiuntive, ma non tutti i metodi sono buoni lì. Fornirò solo il risultato del benchmark JMH qui

 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 

Il numero proviene dall’esecuzione di questo codice:

 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 dir_listFiles() { List 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_walkTree() throws Exception { final List files = new ArrayList<>(1000); for( int i = 0; i < nCycles; i++ ) { Path dir = Paths.get(testDir); files.clear(); Files.walkFileTree(dir, new SimpleFileVisitor () { @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_find() throws Exception { final List 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; } 

Forse potresti scrivere un programma di ricerca di directory in C # / C / C ++ e usare JNI per farlo in Java. Non so se questo migliorerebbe le prestazioni o no.

Bene, o JNI, o, se dici che la tua implementazione è costante, esegui semplicemente “dir” su Windows o “ls” su * nix, con i flag appropriati per elencare solo le directory (Runtime.exec ())

In tal caso, potresti provare una soluzione JNA – un attraversatore di directory dipendente dalla piattaforma (FindFirst, FindNext su Windows) con la possibilità di un pattern di iterazione. Anche Java 7 avrà un supporto del file system molto migliore, vale la pena controllare le specifiche (non ricordo alcun dettaglio specifico).

Modifica: Un’idea: un’opzione è quella di hide la lentezza dell’elenco di directory dagli occhi dell’utente. In un’app lato client, è ansible utilizzare alcune animazioni mentre l’elenco funziona per distrarre l’utente. In realtà dipende da cos’altro l’applicazione fa accanto alla lista.