How to Squeeze Nanoseconds out of a Java Loop

The best tricks are the simplest tricks. So keep reading to be introduced to a simple trick that’s been around for ages — a trick that can cut half the running time from a Java program loop.

Imagine searching through a long list of names. Listing 1 has some code to illustrate the idea.

Listing 1: Searching for a Name

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
public class Main {
  static Scanner diskFile;
  static int MAX_SIZE = 100;
  static String name[] = new String[MAX_SIZE];
  public static void main(String[] args) 
                          throws IOException {
    diskFile = new Scanner(new File("names.txt"));
    int numberOfNames = fillTheArray();
    searchFor("Burd", numberOfNames);
  }
  static int fillTheArray() {
    int i = 0;
    while (diskFile.hasNext() && i < MAX_SIZE) {
      name[i++] = diskFile.next();
    }
    return i;
  }
  static void searchFor(String whatToSearchFor, 
                        int numberOfNames) {
    int i = 0;
    while (i < numberOfNames && 
           !name[i].equals(whatToSearchFor)) {
      i++;
    }
    if (i < numberOfNames) {
      System.out.println("Found at position " + i);
    } else {
      System.out.println("Not found");
    }
  }
}

The code in Listing 1 has an array of names. The number of entries in the array is numberOfNames. The boldface code at the bottom of the listing checks repeatedly for an entry containing the same characters as whatToSearchFor (in this example, the name "Burd").

The loop also checks repeatedly to make sure that i is less than numberOfNames. Without this check, your program's run can come crashing down with a NullPointerException or an ArrayIndexOutOfBoundsException. Here's why:

  • Imagine that the names.txt file contains three names: "Curly", "Larry", and "Moe". Then name[0] is "Curly", name[1] is "Larry", and name[2] is "Moe". There's no name[3] value. (To be more precise, name[3] is null.)

    The value of numberOfNames is 3. Without the i < numberOfNames check, the program checks !name[3].equals(whatToSearchFor). But name[3] is null so the program's run blows up with the NullPointerException.

  • Imagine that the names.txt file contains 100 names, and that MAX_SIZE is 100. Then every entry in the name array contains an honest-to-goodness string. The entries in the name array are name[0], name[1], and so on, all the way up to name[99]. There's no name[100] entry.

    Without the i < numberOfNames check, the program checks !name[100].equals(whatToSearchFor). But name[100] doesn't exist, so the program's run bites the dust with the ArrayIndexOutOfBoundsException.

One way or another, you apparently have to check two things each time through the loop: You have to check if i < numberOfNames and then check if !name[i].equals(whatToSearchFor).

So the big question is, Can you do better? Can you check only one condition instead of two? And the answer (as if you haven't guessed already) is "Yes, you can." This particular trick doesn't reduce the program's running time by leaps and bounds, but it's a cute trick nevertheless. Here's the idea:

Never read in so many names that you don't have at least one empty array entry. Then, after the last honest-to-goodness array entry, add one more entry; namely, the name that you intend to search for. With this extra name at the end of the array, you don't have to keep checking i < numberOfNames. Now the other condition, !name[100].equals(whatToSearchFor), must become false before you run out of array entries.

Listing 2 contains some code to illustrate this idea. (The differences between Listing 2 and Listing 1 are marked in boldface type in Listing 2.)

Listing 2: A Slightly Better Search Routine

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
public class Main {
  static Scanner diskFile;
  static int MAX_SIZE = 100;
  static String name[] = new String[MAX_SIZE];
  public static void main(String[] args) 
                          throws IOException {
    diskFile = new Scanner(new File("names.txt"));
    int numberOfNames = fillTheArray(); 
    searchFor("Burd", numberOfNames);
  }
  static int fillTheArray() {
    int i = 0;
    while (diskFile.hasNext() && i < MAX_SIZE - 1) {
      name[i++] = diskFile.next();
    }
    return i;
  }
  static void searchFor(String whatToSearchFor, 
                        int numberOfNames) {
    name[numberOfNames] = whatToSearchFor;
    int i = 0;
    while (!name[i].equals(whatToSearchFor)) {
      i++;
    }
    if (i < numberOfNames) {
      System.out.println("Found at position " + i);
    } else {
      System.out.println("Not found");
    }
  }
}

In Listing 2, the value MAX_SIZE – 1 insures that the array has at least one empty entry. The statement

name[numberOfNames] = whatToSearchFor;

places the name that you intend to search for after the last honest-to-goodness array entry. And the condition !name[i].equals(whatToSearchFor) checks array entries until it finds either a name from the names.txt file, or the name that you artificially placed after the last entry.

So that's the trick. By adding one extra entry at the end of the list, you go from checking two conditions repeatedly

while (i < numberOfNames && 
       !name[i].equals(whatToSearchFor))

to checking only one condition repeatedly:

while (!name[i].equals(whatToSearchFor))

Here's an interesting fact about the trick described in this article: You don't need a Java program in order to use this trick. In fact, you don't even need a computer! The trick applies to all kinds of situations that involve searching — searching done by computers, searching done by robots, and even searches done by human beings.

Imagine having a long line of boxes, and telling your assistant to find a grapefruit in any of the first hundred boxes. (Tomorrow, someone else will start looking from the 101st box onward.) You can have your assistants count boxes as they search, but who wants to keep track of box counts as they search? If you already know where the 101st box is, put a marker on that box and tell your assistant to search up to the marker. Better yet, put a fake, plastic grapefruit in the 101st box and simply tell your assistant to find a grapefruit.

The same kind of reasoning works in less contrived situations. A recipe for lasagna requires 50 minutes in the oven. You could start heating the lasagna at 5:53pm and look at the clock every minute or so. When at last you've counted off 50 minutes, you take the lasagna out of the oven.

But counting minutes is annoying. While you stare back at the clock, you might miss part of your favorite TV commercial. Instead of doing all this counting, put a marker at the end of the process by setting your kitchen timer to go off in 50 minutes.

You see? It's not just Java. It's common sense.

  • Add a Comment
  • Print
  • Share
blog comments powered by Disqus
Advertisement

Inside Dummies.com

Dummies.com Sweepstakes

Win $500. Easy.