2

I have a program that searches an array of 10 elements for a target from the beginning of the array to the end of the array and then from the end of the array to the beginning of the array. Each time the program is run the array of Strings is shuffled.

I'm clocking the time it takes to find the target for both searches. What I'm finding is that the search from the end of the array to the beginning is always fastest, even if the target is located at the 0 position in the array.

Can someone explain why this is happening?

Here is my 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; 
    long startTime;
    long startTime2;
    long estimatedTime;
    long estimatedTime2;

    /**
     * 
     * @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

        shuffleArray(sa);
        startTime = System.nanoTime();                             // Start speed test
        for(int i = 0; i < sa.length; ++i) {
            //System.out.println("Searching array position: " + i); // Comment out for more accuracy

            if (sa[i].equals(target)) {
                estimatedTime = System.nanoTime() - startTime;    // End speed test
                System.out.println("The target " + "'" + target + // Print target/index to console
                         "'" + " found at array index: "+ i);
                System.out.println("Estimated search time in " +  // Print estimated time
                        "nanoseconds: " + estimatedTime); 

                return i; // return the index of target
            }  
        }
        return -1; // -1 means that target was not found
    }

    /**
     * 
     * @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

        startTime2 = System.nanoTime();                           // Start speed test
        for(int i = 9; i < sa.length; --i) {
            //System.out.println("Searching array position: " + i); // Comment out for more accuracy

            if (sa[i].equals(target)) {
                estimatedTime2 = System.nanoTime() - startTime2;  // End speed test
                System.out.println("The target " + "'" + target2
                        + "'" + " found at array index: " + i);   // Print to console
                System.out.println("Estimated search time in " +  // Print estimated time
                        "nanoseconds: " +estimatedTime2); 

                return i; // return the index of target
            }
        }
        return -1; // -1 means that target was not found
    }

    /**
     * 
     * @param estimatedTime - estimated time of search beginning to end
     * @param estimatedTime2 - estimated time of search end to beginning 
     * @return fastest method 
     */
    String deduceFastestSearchMethod(long estimatedTime, long estimatedTime2) {
        if(estimatedTime < estimatedTime2) {
            return "linearStringSearch found " + "'"
                + target + "'" + " fastest";
        }   
        return "backwardLinearStringSearch found " + 
            "'" + target + "'" + " fastest";
    }

    // Implement Fisher–Yates shuffle
    public void shuffleArray(String[] sa){      
        Random rnd = new Random();      
        for (int i = sa.length - 1; i > 0; i--){
            int index = rnd.nextInt(i + 1);

            // Simple swap
            String a = sa[index];
            sa[index] = sa[i];
            sa[i] = a;
        }
    }

    /*
     * 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     
        lss.linearStringSearch("mouse", lss.randomStrings);          // Pass arguments       

        // Search array from end to beginning
        System.out.println("\nBackwards linear search: ");          // Print title
        lss.backwardLinearStringSearch("mouse", lss.randomStrings); // Pass arguments   

        // Print fastest search
        System.out.println();
        System.out.println(lss.deduceFastestSearchMethod(lss.estimatedTime, lss.estimatedTime2));
    }   
}

Here is a test output:

Linear search: 
The target 'mouse' found at array index: 0
Estimated search time in nanoseconds: 9058

Backwards linear search: 
The target 'mouse' found at array index: 0
Estimated search time in nanoseconds: 4982

backwardLinearStringSearch found 'mouse' fastest

Here is another test output:

Linear search: 
The target 'mouse' found at array index: 8
Estimated search time in nanoseconds: 12229

Backwards linear search: 
The target 'mouse' found at array index: 8
Estimated search time in nanoseconds: 3170

backwardLinearStringSearch found 'mouse' fastest
LooMeenin
  • 818
  • 3
  • 17
  • 33
  • 2
    Just curious, what happens if you call `backwardLinearStringSearch` first and then call `linearStringSearch`? Perhaps it is caching the variables so that is why it is quicker the second time. – mdewitt Jan 23 '14 at 20:24
  • 3
    Try swapping the order of the two algorithms. Maybe it's just the JVM warming up. – pamphlet Jan 23 '14 at 20:24
  • I'm not an expert, but are you sure you should call a `new Random()` every time? What happens if you move it to the main? – Leeor Jan 23 '14 at 20:29
  • 5
    There are few errors in your benchmark. You should read about [how-do-i-write-a-correct-micro-benchmark-in-java](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). You are not letting JVM to warm up and load each class before using it in benchmark. If I move `backwardLinearStringSearch` before `linearStringSearch` I get better results for `linearStringSearch`. – Pshemo Jan 23 '14 at 20:32
  • 2
    Any Java benchmark taking less than some milliseconds is a complete non-sense. You're measuring the code warm-up, nothing else. Repeat the trial for one second, drop the results, and repeat it again. – maaartinus Jan 23 '14 at 20:33
  • 1
    I swapped the methods in main and now I am getting the opposite result – LooMeenin Jan 23 '14 at 20:33
  • As others have said, this is a meaningless test as written becuase it doesn't wait until JITting has occurred before measuring. And that isn't the end of the problems -- since hotspot JIT compilers may reoptimize the code after it has been running for a while, based on profiling data, tests really need to run with something close to real-world "typical" input data to produce meaningful performance results. Even worse, JIT optimization is somewhat nondeterministic. Basically, tiny performance tests like this one are utterly meaningless in Java; either do it right or don't bother. – keshlam Jan 23 '14 at 21:28

0 Answers0