1
\$\begingroup\$

I've written a program:

import java.io.File;
import java.io.FilenameFilter;
import java.io.IOException;
import java.util.ArrayList;
import org.apache.commons.io.FileUtils;

/**
 *
 * @author Mohammad Faisal
 */
public class FileContentMatcher {

public static void main(String[] args) throws IOException {

    String textToMatch = "Quick Styles gallery on";
    ArrayList<String> paths = new ArrayList<String>();
    String content;
    int found = 0;
    int notFound = 0;
    FilenameFilter filter = new FilenameFilter() {
        public boolean accept(File dir, String name) {
            return name.endsWith(".txt");
        }
    };

    File path = new File("E:\\anchit\\temp");
    File[] listOfFiles = path.listFiles(filter);
    for (File file : listOfFiles) {
        content = FileUtils.readFileToString(file);
        if (content.contains(textToMatch)) {
            //System.out.println("Found in: " + file.getAbsolutePath());
            paths.add(file.getAbsolutePath());
            found++;
        } else {
            //System.out.println("No found\n" + content);
            notFound++;
        }
    }
    for (String pth : paths) {
        System.out.println(pth);
    }
    System.out.println("Found in " + found + " files.\nNot found in " + notFound + " files.");
}
}

In which I've used Apache Commons IO api.
My actual requirement is to list all the files in the given directory which contains the search phrase textToMatch in minimum amount of time about 4-5 seconds, where number of files could be upto 100000. But this program takes much more time than that.
So I need to optimize this code but not getting how?
Is there any API which can help me? I've heard of Lucene but not getting how to work with it.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ well, the number of files doesn't tell how many GB/TB of data you need to go through; and how many seconds does you program currently take? \$\endgroup\$
    – dnozay
    Jul 15, 2013 at 6:45
  • 2
    \$\begingroup\$ With no constraints or control over the organization of data, you are unlikely to get those levels of performance. Opening some random file takes roughly 10 ms. 10^5 X 10^-2 secs ~ 15 mins. (Performance is known to be hard to predict, but do not expect to get anything less than several minutes without doing something different.) Consider also using full-text indexes. \$\endgroup\$ Jul 15, 2013 at 6:51
  • \$\begingroup\$ @abuzittingillifirca: well I've no idea of full-text indexes. How do it works? \$\endgroup\$ Jul 15, 2013 at 7:02
  • 2
    \$\begingroup\$ Lucene is the index&search Java library which I hear most about, but I've never used it. MS SQL Server (I've used its full-text indexes) (and probably other RDBMSs) ship with full-text indexing and search. There probably are simpler solutions probably but it totally depends on what your constraints are [Is mirroring the directory in Ramdisk and doing a grep an acceptable solution, where would we know?]. And that deep an analysis is beyond the scope of Code Review SE. You may try Programmers SE. \$\endgroup\$ Jul 15, 2013 at 11:00
  • 1
    \$\begingroup\$ I would suggest you would, if you could ;) You should really try programmers.stackexchange.com for some other ideas; since your problem size, as @dnozay and I have pointed out, requires more than simple optimizations to achieve the performance you expect from common systems. \$\endgroup\$ Jul 15, 2013 at 11:09

3 Answers 3

4
\$\begingroup\$

As poined out in the comments, your current approach might be too slow for your goal of "about 4-5 seconds". Depending on what's your actual use case, using an index might indeed be a good idea. This is similar to how internet search engines do it.

To create the index:

  • create a map Map<String, List<File>> for holding the association of search terms to files
  • go through all your files, and for each word in each file, add that file to the list corresponding to that word in your index map
  • you might want to skip common words, such as "a", "and", "the", etc., or you could even apply a stemmer to drastically reduce the variability in words

Once you've created the index (which could take quite some time), you just have to look up the search word in that index to get the list of files that contain the word (or a linguistic variant of it, if you used a stemmer).

As said before, the applicability of this approach depends heavily on your actual use case. If the files contain genetic sequences and you are searching a certain pattern, this probably won't help much. Even if you are searching for some complex phrase this might not work, as you'd have to add each possible (sub) phrase to the index. But if you are looking for individual words in ordinary text files (or HTML or the like) this might work.

Update: Since you seem to indeed search for complex phrases, you could try the following:

  • create the index, as desribed above, optionally using a stemmer
  • search for each word in your phrase (or the stemmed version thereof) in your index
  • for each file that, according to your index, contains all the words, do a full-text search for the original phrase

Finally, if this still does not cut it, you could also create indexes for word bigrams or even trigrams.

\$\endgroup\$
1
\$\begingroup\$

A few tips :

  • Instead of reading the entire file into memory, use a Reader, reading only a small buffer at a time, to check for possible matches. This will improve memory usage, and avoid reading the entire file if the textToMatch is found.
  • Separate the code that loops over the files, from the code that checks a file. Use multiple threads that check files. This is an ideal candidate for the producer-consumer pattern (using a blocking queue) with one producer, and multiple consumers.
\$\endgroup\$
0
\$\begingroup\$

If you are hitting a bottleneck in terms of sheer hardware, you may move to a distributed model using MapReduce. It works just like a distributed awk / grep conceptually. Enter big words like Big Data, which really is trading compute time on one machine (expensive one most of the time) with less compute time on more machines (commodity hardware most of the time) by following divide-and-conquer principles.

Here is a link to a Hadoop tutorial.

I wouldn't take this route unless you have identified that your solution is going to hit the limits. But consider this:

  • what happens if your files grow over time?
  • what happens if your have more files over time?

Distributed systems scale horizontally (number of machines) whereas a single machine does not scale well vertically (single machine specs ~ $$$).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.