3

I wrote a program for a Java class that I am taking to search a String array for a specific target. The program searches for the target from the beginning of the array to the end of the array and then searches from the end of the array to the beginning of the array. I am supposed to test the speed of both searches to see which one is faster. How can I test this?

Here is the program: 

public class LinearStringSearch {

    // Array filled with random Strings
    String[] randomStrings = {"apple", "yellow", "fire", "wood", "zinc", 
            "ram", "mouse", "fish", "cheese", "dirt"};

    // Save target arguments for global access(console printing purposes)
    String target;  
    String target2; 

    /**
     * 
     * @param target - the item you want to retrieve from array
     * @param sa - the name of the array
     * @return i - the target, otherwise return error code: -1
     */
    int linearStringSearch(String target, String[] sa) {
          this.target = target;  // set class variable for print access
          for(int i = 0; i < sa.length; ++i) {
             System.out.println("Searching array position: " + i);
             if (sa[i].equals(target)) {
              // System.out.println("Target found! ");
               return i;
             }   
          }
          return -1;
    }

    /**
     * 
     * @param target - the item you want to retrieve from array
     * @param sa - the name of the array
     * @return i - the target, otherwise return error code: -1
     */
    int backwardLinearStringSearch(String target, String[] sa) {
        this.target2 = target;  // set class variable for print access
        for(int i = 9; i < sa.length; --i) {
            System.out.println("Searching array position: " + i);
            if (sa[i].equals(target)) {
                return i;
            }
        }
        return -1; // -1 means that target was not found
    }

     /*
      * The target string is searched from the beginning of the array to the end of the array, then
      * from the end of the array to the beginning of the array. 
      */
    public static void main(String[] args) {

        LinearStringSearch lss = new LinearStringSearch();

        // Search array from beginning to end
        System.out.println("Linear search: ");                          // Print title  
        int index = lss.linearStringSearch("mouse", lss.randomStrings); // Pass arguments
        System.out.println("The target " + "'" + lss.target + "'" +     // Print to console
        " found at array index: "+index);    

        // Search array from end to beginning
        System.out.println("\nBackwards linear search: ");                       // Print title
        int index2 = lss.backwardLinearStringSearch("mouse", lss.randomStrings); // Pass arguments
        System.out.println("The target " + "'" + lss.target2 + "'" +             // Print to console
        " found at array index: "+index2); 
    }   
}

Here is the output: 

Linear search: 
Searching array position: 0
Searching array position: 1
Searching array position: 2
Searching array position: 3
Searching array position: 4
Searching array position: 5
Searching array position: 6
The target 'mouse' found at array index: 6

Backwards linear search: 
Searching array position: 9
Searching array position: 8
Searching array position: 7
Searching array position: 6
The target 'mouse' found at array index: 6
LooMeenin
  • 818
  • 3
  • 17
  • 33

2 Answers2

2

JVM is very complex, so if you want to get accurate and real results you have to remember about JIT impact. This mean that you need to test code that is already optimized by JIT, and wont be changed during method timing. So you have to write microbenchmark - you can use libraries like Caliper or JMH. In this case in Caliper it will look like that:

public class MyBenchmark extends Benchmark {
    public void timeMyOperation(int reps) {
      for (int i = 0; i < reps; i++) {
        int index = lss.linearStringSearch("mouse", lss.randomStrings);;
      }
   }
}
Community
  • 1
  • 1
Jakub Kubrynski
  • 13,724
  • 6
  • 60
  • 85
2

Take a look at Java Performance Testing. System.currentTimeMillis() or better getCurrentThreadCpuTime() is your friend. If the time difference is too small, consider running each test multiple times and compare how long that takes.

Community
  • 1
  • 1
Tobias
  • 4,999
  • 7
  • 34
  • 40
  • 2
    Or use `System.nanoTime()` for greater resolution – Java Devil Jan 21 '14 at 22:13
  • You're wrong - if you want to use such solution when you have to manually implement jvm warmup, analyse JIT impact, etc - finally your results wont be accurate – Jakub Kubrynski Jan 21 '14 at 22:14
  • 2
    +1. I suggest removing System.out.println calls from within the functionality to be measured as this will alter the execution such that you are not just measuring the speed of the search. – Jason Jan 21 '14 at 22:15
  • 1
    *If you are measuring elapsed time, and you want it to be correct, you must use System.nanoTime(). You cannot use System.currentTimeMillis(), unless you don't mind your result being wrong.* http://stackoverflow.com/a/13674788/516167 – MariuszS Jan 21 '14 at 22:21
  • @Tobias, read answer from **your** attached question, they are recommending `getCurrentThreadCpuTime` instead of `currentTimeMillis`! – MariuszS Jan 21 '14 at 22:24
  • Read my comments one more time, don`t use `currentTimeMillis`! – MariuszS Jan 22 '14 at 08:33
  • I agree that it might not be as precise, but it all depends on the use case. All the OP wanted to know is which of the two methods is faster. If you run both of the operations, say, a thousand times, you might already find a huge time difference which might be big enough to get the job done and to make a statement about which method is faster. – Tobias Jan 22 '14 at 18:23