比创建文件列表更好的文件搜索算法

Question

对于我正在做的项目,我创建了一个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";
}

Answer 1

有一种方法可以walkFileTree()在JDK7中调用.

引用Java教程:

要遍历文件树,首先需要实现一个FileVisitor.A 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()调用方法".

Answer 2

有两种算法.深度优先搜索和广度优先搜索.
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search

对于您的问题,这些算法的时间效率为O(n).更好是不可能的.但是你可以构建二叉树.然后你的搜索效率是O(logn).但首先,您必须留出时间进行二叉树构建.如果只搜索一个,请不要使用二叉树.