Лучший алгоритм поиска файлов, чем создание списка файлов

Для проекта, который я делаю, я сделал программу Java, которая ищет файл, указанный пользователем.

Код начинает поиск в базовом каталоге, указанном пользователем (т.е.: C:). Он перебирает все файлы в этом каталоге, проверяя, соответствует ли имя файла поисковому запросу, заданному пользователем, и если оно совпадает, абсолютный путь к файлам добавляется в строку. Если файл является каталогом, он добавляется в список, который будет рассмотрен позже.

Когда поиск в базовой папке завершен, он будет искать/удалять первый каталог в списке таким же образом (снова добавляя все найденные каталоги в список) и продолжает до тех пор, пока не останется каталогов для поиска. Затем отображение найденных файлов пользователю.

Мой вопрос; есть ли лучший способ поиска файлов? Возможно, искать каталоги сразу, а не добавлять их в список? Буду рад любому совету, заранее спасибо! Вот мой код.

public String SearchDir(File directory){
    this.directory = directory;
    do{
        File[] files = this.directory.listFiles();
        if(files != null){
            for(int i = 0; i < files.length; i++){

                // The current file.
                File currentFile = files[i];

                // The files name without extension and path
                // ie C:\Documents and Settings\myfile.file = myfile
                String fileName = this    .removeExtension(this.removePath(currentFile.getName()));


                // Don't search hidden files
                if(currentFile.isHidden()){
                    continue;
                }
                System.out.println(currentFile.getAbsolutePath());

                // Check if the user wanted a narrow search
                if(this.narrow){
                    // Narrow search = check if the file STARTS with the     string given.
                        if(fileName.toLowerCase().startsWith(this.fileName.toLowerCase())){
                    this.found += currentFile.getAbsolutePath() + '\n';
                    this.foundXTimes++;
                }
            }
            else{
                // Non-Narrow search = check for the given string ANYWHERE in the file name.
                if(fileName.toLowerCase().contains(this.fileName.toLowerCase())){
                    this.found += currentFile.getAbsolutePath() + '\n';
                    this.foundXTimes++;
                }
            }

                // If the file is a directory add it to the buffer to be     searched later.
                if(currentFile.isDirectory()){
                    this.directoriesToSearch.add(currentFile);
                }
            }

            if(!this.directoriesToSearch.isEmpty()){
                this.directory = this.directoriesToSearch.remove(0);    
            }
        }
    } while(!this.directoriesToSearch.isEmpty());

    if(!this.found.equals(""))
        return this.found;
    else
        return "x";
}

java file search
person Austin    schedule 27.05.2013    source источник
comment
Если вы используете Java7, Files.walkFileTree(Path, SimpleFileVisitor<Path>) сделает все за вас;)   -  person Marco    schedule 27.05.2013
comment
Я думаю, что есть два способа сделать это: 1. Линейно искать в файловой иерархии на ходу (именно так вы это делаете) или 2. Загружать данные в структуру данных (например, двоичное дерево) и искать данные там. Недостатком первого подхода является то, что обход всей иерархии может занять много времени, но вы делаете это только один раз (но вы делаете это один раз для каждого поиска). Минус второго подхода в том, что может потребоваться много времени для загрузки полной иерархии в структуре данных, но зато можно много раз искать данные в структуре (хотя периодически нужно ее обновлять).   -  person Barranka    schedule 27.05.2013
comment
То, что вы делаете, - это поиск в ширину, поиск в каталогах сразу будет поиском в глубину, и это не лучше, как вы хотите, чтобы ваше дерево искалось.   -  person Djon    schedule 27.05.2013

Ответы (2)


arrow_upward
6
arrow_downward

Есть два алгоритма. Поиск в глубину и поиск в ширину.
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Поисквширину

Эффективность этих алгоритмов по времени составляет O (n) для вашего вопроса. Лучше невозможно. Но вы можете построить бинарное дерево. Тогда эффективность вашего поиска равна O(logn). Но во-первых, вы должны выделить время для построения бинарного дерева. Если вы ищете только один, не используйте бинарное дерево.

person Muzaffer    schedule 27.05.2013
comment
Существует также итеративный поиск с углублением. ;-) хорошо, я бы не стал использовать его в этом случае, но теперь кое-что конструктивное: если вы решите построить индекс, не используйте просто такое простое двоичное дерево. Вместо этого используйте деревья или попытки Patricia, а затем используйте механизм сопоставления, который использует структуру индекса. Или хранить все в базе данных, которая все сделает за вас. - person kutschkem; 27.05.2013
comment
Как сказал Кучкем, база данных — хорошее решение. База данных выбирает лучшую структуру для ваших данных. Тогда просто используйте запрос :) - person Muzaffer; 27.05.2013

arrow_upward
5
arrow_downward

Существует метод, который вы можете расширить под названием walkFileTree() в JDK7.

Цитата из учебников по Java:

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

  • preVisitDirectory. Вызывается перед посещением записей каталога. * postVisitDirectory. Вызывается после посещения всех записей в каталоге. Если возникают какие-либо ошибки, в метод передается конкретное исключение. * visitFile. Вызывается для посещаемого файла. BasicFileAttributes файла передается методу, или вы можете использовать пакет атрибутов файла для чтения определенного набора атрибутов. Например, вы можете прочитать DosFileAttributeView файла, чтобы определить, установлен ли в файле «скрытый» бит. * `visitFileFailed. Вызывается, когда файл недоступен. Конкретное исключение передается методу. Вы можете выбрать, генерировать ли исключение, выводить его на консоль или в файл журнала и т. д.

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

Следующий код не мой, он взят из здесь, но это поясняющий пример того, как пройтись по всем файлам в пути:

import java.io.IOException;
import java.nio.file.FileVisitResult;
import java.nio.file.FileVisitor;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.SimpleFileVisitor;
import java.nio.file.attribute.BasicFileAttributes;

/** Lists all files in the given directory recursively.
 * .svn directories are ignored.
 */
public class Find extends SimpleFileVisitor<Path> {

 /** Main program.
  * @param args Command line arguments - directories to search.
  */
 public static void main(final String... args) throws IOException {
     final FileVisitor<Path> fileVisitor = new Find();
     for (final String arg : args.length > 0 ? args : new String[] {"."}) {
         final Path root = Paths.get(arg);
         Files.walkFileTree(root, fileVisitor);
     }
 }

 /** {@inheritDoc} */
 public FileVisitResult preVisitDirectory(final Path dir,
                                          final BasicFileAttributes attrs) {
     if (".svn".equals(dir.getFileName().toString())) {
         return FileVisitResult.SKIP_SUBTREE;
     }
     System.out.println(dir);
     return FileVisitResult.CONTINUE;
 }

 /** {@inheritDoc} */
 public FileVisitResult visitFile(final Path file,
                                  final BasicFileAttributes attrs) {
     System.out.println(file);
     return FileVisitResult.CONTINUE;
 }

Автор этого кода указывает, что «метод visitFile() не вызывается для каталогов. Для каталогов вызывается метод preVisitDirectory()».

person J. A. Corbal    schedule 27.05.2013