Better file search algorithm than creating a list of files

Question

For a project I'm doing I made a java program that searches for a file specified by user input.

The code starts searching in a base directory specified by the user (ie: C:). It loops through all the files in this directory checking if the filename matches the search term given by the user, if it does match, the files absolute path is added to a string. If the file is a directory it is added to a list to be dealt with later.

When the base folder is finished being searched it will search/remove the first directory in the list in the same way (adding any directories found to the list once again) and continues until there are no more directories to search. Then displaying the files found to the user.

My question; is there a better way to search for files? Perhaps searching directories immediately instead of adding them to the list? Any advice would be awesome, thanks in advance! Here's my code.

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

If you are using Java7, Files.walkFileTree(Path, SimpleFileVisitor<Path>) does everything for you ;) — Marco
– Marco, Commented May 27, 2013 at 14:57
I think there are two ways to do it: 1. Search the file hierarchy linearly "on the go" (which is the way you are doing it), or 2. Load the data in a data structure (like a binary tree) and search the data there. The downside of the first approach is that it can take a long time to traverse the entire hierarchy, but you only do it once (but you do it once for every search). The downside of the second approach is that it can take a long time to load the full hierarchy in the data structure, but you can search many times the data in the structure (although you need to update it periodically). — Barranka
– Barranka, Commented May 27, 2013 at 14:59
What you're doing is a breadth-first search, searching directories immediately would be a depth-first search, neither is better, just how you want your tree searched. — Djon
– Djon, Commented May 27, 2013 at 15:05

Muzaffer · Accepted Answer · 2013-05-27 15:14:50Z

6

There are two algorithms. Depth first search and breadth first search.
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search

These algorithms time efficiency is O(n) for your question. Better is imposible. But you can build binary tree. Then your search's efficiency is O(logn). But firstly, you have to allow time for binary tree building. If you search only one, dont use binary tree.

answered May 27, 2013 at 15:14

Muzaffer

1,4471 gold badge13 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

kutschkem Over a year ago

There is also Iterative Deepening Search. ;-) ok i wouldn't really use it in this case, but now for something constructive: If you do decide to build an index, don't just use a plain binary tree like that. Use Patricia trees or tries instead, and then use a matching engine that exploits the index's structure. Or store erverything in a database, which will do everything for you.

Muzaffer Over a year ago

As kutschkem said, database is good solution. Database choose a better structure for your datas. Then just use query :)

J. A. Corbal · Accepted Answer · 2013-05-27 16:06:25Z

There is a method you can extend called walkFileTree() in JDK7.

Quoting the Java Tutorials:

To walk a file tree, you first need to implement a FileVisitor. A FileVisitor specifies the required behavior at key points in the traversal process: when a file is visited, before a directory is accessed, after a directory is accessed, or when a failure occurs. The interface has four methods that correspond to these situations:

preVisitDirectory. Invoked before a directory's entries are visited. * postVisitDirectory. Invoked after all the entries in a directory are visited. If any errors are encountered, the specific exception is passed to the method. * visitFile. Invoked on the file being visited. The file's BasicFileAttributes is passed to the method, or you can use the file attributes package to read a specific set of attributes. For example, you can choose to read the file's DosFileAttributeView to determine if the file has the "hidden" bit set. * `visitFileFailed. Invoked when the file cannot be accessed. The specific exception is passed to the method. You can choose whether to throw the exception, print it to the console or a log file, and so on.

If you don't need to implement all four of the FileVisitor methods, instead of implementing the FileVisitor interface, you can extend the SimpleFileVisitor class. This class, which implements the FileVisitor interface, visits all files in a tree and throws an IOError when an error is encountered. You can extend this class and override only the methods that you require.

The following code is not mine, it comes from here, but it's a clarifying example of how to walk through all files in the path:

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

The author of this code points that "the method visitFile() is not invoked for directories. For directories, method preVisitDirectory() is invoked."

Collectives™ on Stack Overflow

Better file search algorithm than creating a list of files

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related