Как получить список каталогов БЫСТРО в Java?

Question

Предположим, что очень простая программа, которая перечисляет все подкаталоги данного каталога. Звучит достаточно просто? За исключением единственного способа перечисления всех подкаталогов в Java, это использовать FilenameFilter в сочетании с File.list () .

Это работает для тривиального случая, но когда в папке, скажем, 150 000 файлов и 2 подпапки, глупо ждать там 45 секунд, перебирая все файлы и тестируя для file.isDirectory (). Есть ли лучший способ перечислить подкаталоги ??

---

PS. Извините, пожалуйста, сохраните лекции, если в одном каталоге слишком много файлов. Наша живая среда имеет это как часть требования.

Answer 1

Как уже упоминалось, это в основном аппаратная проблема. Доступ к диску всегда медленный, и большинство файловых систем не предназначены для работы с каталогами с таким количеством файлов.

Если вам по какой-то причине нужно хранить все файлы в одном каталоге, я думаю, вам придется поддерживать свой собственный кэш. Это можно сделать с помощью локальной базы данных, такой как sqlite, HeidiSQL или HSQL. Если вы хотите максимальной производительности, используйте java TreeSet и кешируйте его в памяти. Это означает, что по крайней мере вам придется читать каталог реже, и это может быть сделано в фоновом режиме. Вы можете уменьшить необходимость обновления списка еще больше, используя собственный системный API уведомлений об обновлениях файлов (inotify в linux) для подписки на изменения в каталоге.

Это кажется невозможным для вас, но однажды я решил похожую проблему, "хешируя" файлы в подкаталогах. В моем случае задача состояла в том, чтобы сохранить пару миллионов изображений с числовыми идентификаторами. Я построил структуру каталогов следующим образом:

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

Это хорошо сработало для нас, и это решение, которое я бы рекомендовал. Вы можете сделать что-то похожее на буквенно-цифровые имена файлов, просто взяв первые две буквы имени файла, а затем следующие две буквы. Я тоже так делал однажды, и это тоже сделало.

Answer 2

Знаете ли вы конечный список возможных имен подкаталогов? Если это так, используйте цикл для всех возможных имен и проверьте наличие каталога.

В противном случае вы не можете получить ТОЛЬКО имена каталогов в большинстве базовых ОС (например, в Unix, список каталогов просто читает содержимое файла «directory», поэтому нет способа быстро найти «only directory» без перечисления всех файлов ).

Однако в NIO.2 в Java7 (см. http://java.sun.com/developer/technicalArticles/javase/nio/#3) есть способ создать список потоковых каталогов, чтобы не получить полный массив файловых элементов, загромождающих вашу память / сеть.

Answer 3

На самом деле есть причина, по которой вы читаете лекции: это правильный ответ на вашу проблему. Вот предыстория, так что, возможно, вы сможете внести некоторые изменения в вашу живую среду.

Первое: каталоги хранятся в файловой системе; думать о них как о файлах, потому что это именно то, что они есть. Когда вы перебираете каталог, вы должны прочитать эти блоки с диска. Каждой записи каталога потребуется достаточно места для хранения имени файла, разрешений и информации о том, где этот файл находится на диске.

Второе: каталоги не хранятся с каким-либо внутренним порядком (по крайней мере, не в файловых системах, где я работал с файлами каталогов). Если у вас есть 150 000 записей и 2 подкаталога, эти 2 ссылки на подкаталоги могут быть где угодно в пределах 150 000. Вы должны выполнить итерацию, чтобы найти их, и тут нет пути.

Итак, допустим, что вы не можете избежать большого каталога. Ваша единственная реальная возможность - попытаться сохранить блоки, составляющие файл каталога, в кеше в памяти, чтобы вы не обращались к диску при каждом обращении к ним. Вы можете добиться этого, регулярно перебирая каталог в фоновом потоке - но это приведет к чрезмерной нагрузке на ваши диски и помешает другим процессам. Кроме того, вы можете отсканировать один раз и отслеживать результаты.

Альтернативой является создание многоуровневой структуры каталогов. Если вы посмотрите на коммерческие веб-сайты, вы увидите URL-адреса, такие как /1/150/15023.html - это означает, что количество файлов в каталоге будет небольшим. Думайте об этом как об индексе BTree в базе данных.

Конечно, вы можете скрыть эту структуру: вы можете создать слой абстракции файловой системы, который принимает имена файлов и автоматически генерирует дерево каталогов, в котором можно найти эти имена.

Answer 4

Ключевой проблемой может быть функция File.isDirectory (), вызываемая в цикле.

File.isDirectory () может быть очень медленным. Я видел, как NFS потребовалось 10 секунд, чтобы обработать каталог 200 файлов.

Если вы можете во что бы то ни стало предотвратить вызовы File.isDirectory () (например, проверка на расширение, отсутствие расширения == каталог), вы можете резко повысить производительность.

В противном случае я бы предложил сделать JNA / JNI / написать собственный скрипт, который сделает это за вас.

Библиотека jCifs позволяет более эффективно управлять сетевыми ресурсами Windows. Мне неизвестна библиотека, которая бы делала это для других сетевых файловых систем.

Answer 5

Я не знаю, поглотит ли это накладные расходы на cmd.exe, но одна возможность будет примерно такой:

...
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 означает поиск в подкаталогах
• / ad означает только возврат каталогов
• / b означает возврат полного пути из корня

Answer 6

Вы могли бы взломать его, если бы все 150k файлы (или их значительное количество) имели похожее соглашение об именах, например:

*.jpg
*Out.txt

и фактически создает файловые объекты только для тех, в которых вы не уверены, что являетесь папкой.

Answer 7

Я сталкивался с подобным вопросом при отладке производительности в Java-приложении, перечисляющем множество файлов. Использует старый подход

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

И похоже, что каждый f.isDirectory () - это вызов родной FileSsystem, который, по крайней мере в NTFS, очень медленный. Java7 NIO имеет дополнительный API, но не все методы хороши. Я просто предоставлю результаты теста JMH здесь

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

Номер исходит от исполнения этого кода:

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;
}

Answer 8

если ваша ОС стабильна, попробуйте JNA :

• opendir / readdir в UNIX
• FindFirstFile и связанный API в Windows
• Java7 с NIO2

это все «потоковые API». Они не заставляют вас выделять список или массив из 150 тыс. Перед началом поиска. ИМХО, это большое преимущество в вашем сценарии.

Answer 9

Это нестандартное решение, которое не требует каких-либо испытаний. Это также зависит от наличия файловой системы, которая поддерживает символические ссылки. Это не решение Java. Я подозреваю, что ваша проблема связана с файловой системой / ОС, а не с Java.

Можно ли создать параллельную структуру каталогов с подкаталогами, основанными на начальных буквах имен файлов, а затем символически связать с реальными файлами? Иллюстрация

/symlinks/a/b/cde

будет ссылаться на

/realfiles/abcde

(где / realfiles находится там, где находятся ваши 150 000 файлов)

Вы должны будете создать и поддерживать эту структуру каталогов, а у меня недостаточно информации, чтобы определить, насколько это практично. Но приведенное выше создаст быстрый (er) индекс в вашем неиерархическом (и медленном) каталоге.

Answer 10

есть также рекурсивное параллельное сканирование на http://blogs.oracle.com/adventures/entry/fast_directory_scanning. По существу, братья и сестры обрабатываются параллельно. Там также обнадеживающие тесты производительности.