Efficient File Searching

Question

During an interview I was asked to consider the following:

You are trying to find an instance of an error code within a number of log files within a directory. The goal is to count the number of times that the error code appears within the specified files.

For the written function, it was to be passed the following arguments (the directory and general file naming convention were known):

[TimeStamp]: String

[ErrorCode]: String

Afterward I went home and coded up a basic implementation of a single file search algorithm with, I believe, O(1) search time after the files are parsed. Does this implementation make sense, and is it correct in terms of Java 8?

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;
/**
 * Created by Brendan on 5/13/2016.
 *
 * A quick implementation of an interview File Search algorithm.
 * Parses the file into a hash map so that occurrences of a phrase
 * can be quickly looked up.
 */
public class FileSearch {
    public static void main(String[] args) {
        Map<String, Long> wordMap = new HashMap<>();
        try {
            wordMap = populateWordMap("C:\\Projects\\logs\\app-log.log");
        } catch(IOException e) { }

        System.out.println("Total unique words found: " + wordMap.size());
        System.out.println("Most popular word: " + findMostPopularWord(wordMap));
    }

    private static String findMostPopularWord(Map<String, Long> wordMap) {
        return wordMap.entrySet()
                        .stream()
                        .max(Map.Entry.comparingByValue())
                        .get().getKey();
    }

    private static Map<String, Long> populateWordMap(String filePath) throws IOException {
        return Files.lines(Paths.get(filePath))
                .map((wholeLine) -> wholeLine.split(" "))
                .map((lineArray) -> mapWordsInLine(lineArray))
                .map(Map::entrySet)
                .flatMap(Collection::stream)
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (m1, m2) -> m1 + m2));
    }

    private static Map<String, Long> mapWordsInLine(String[] lineArray) {
        return Arrays.stream(lineArray)
                    .collect(Collectors.groupingBy(String::toString, Collectors.counting()));
    }
}

Answer 1

Comments about your current code first:

Closing the Stream

The method Files.lines(path) returns a Stream<String> over the lines of the file. This stream should be closed because it encapsulates a Reader of the file. The documentation mentions that:

If timely disposal of file system resources is required, the try-with-resources construct should be used to ensure that the stream's close method is invoked after the stream operations are completed.

Therefore, the method populateWordMap should be using a try-with-resources:

try (Stream<String> stream = Files.lines(Paths.get(filePath))) {
    // ...
}

Allocating unused objects

You currently allocate the wordMap with a new hash map, and then store the result of invoking populateWordMap in it.

Map<String, Long> wordMap = new HashMap<>();
try {
    wordMap = populateWordMap("C:\\Outils\\eclipse-mars\\workspace\\test\\text.txt");

The consequence is that the first hash map that was created for nothing: it is unused and will be garbage collected. Best not to create it in the first place.

Empty catch blocks

try {
    // something
} catch(IOException e) { }

is generally not a good idea: you are completely swallowing the exception that could be thrown and giving no information. You could log the exception to tell what went wrong; you could also rethrow it; or you could even let the main method throw it, since there is really nothing you can do at this level when something wrong happens.

Handling empty Optional

Your findMostPopularWord method is searching for the word appearing the most times. It works by correctly using the max operation. But then, you have:

.max(Map.Entry.comparingByValue()).get().getKey();

To get the key of the entry having the max value. The problem is that when the Stream is empty, max will return an empty Optional and the explicit call to .get() will throw an exception. This raises the more general question of what you want to happen where the scanned file is empty (and contains no words). Among the possible solutions: just return null or throw a custom exception. For those two solutions, you can use .orElse(null) or orElseThrow(...), instead of get.

Looping over all files in a directory

I'll note that your current solution only works by counting word occurences in a single file when the original task was to do it for all files in a directory. For that enhancement, you can use Files.list(path) which returns a Stream<Path> of all the files under the given path.

---

The current flow of your code is:

• Loop over each line of the file
• Split each line in an array of words
• Replace each array of words with a map containing the occurrences of each word
• Replace each of those map with another map containing the occurrences of each entry's value.

This is not very efficient: you are converting each line into a map, only to disregard them later and create another map out of all those maps.

The problem is that you're thinking in terms of "line in a file" when the actual task is to count space separated words. For this task, you can use a Scanner:

private static Map<String, Long> populateWordMap(String filePath) throws IOException {
    try (Scanner scanner = new Scanner(Paths.get(filePath))) {
        Iterable<String> iterable = () -> scanner;
        return StreamSupport.stream(iterable.spliterator(), false)
                     .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }
}

A scanner tokenize by default around single spaces. We can then convert the scanner (which is an Iterator) to a Stream and group by each word while counting their occurences.