1
\$\begingroup\$

I implemented a binary search algorithm. And did it using recursive and non-recurcive approaches. Then I compared the performance of both implementations with java out-of-the-box solution. And what I got is my implementations execute for pretty the same time as Arrays.binarySearch(), which seems to be perfectly valid result as far as the execution lasts only for log(n) time. Despite the theoretical conclusions, I am still in doubts. Are the implementations good enough and how can I heavy load the test case to notice any, let it be tiny, distinction?

Any feedback and suggestions are highly appreciated.

import java.time.*;
import java.time.temporal.*;
import java.util.*;
import java.util.stream.*;

//The program has two modes: recursive and ordinary.
//One can choose recursive mode using command line argument R.
//Or, skipping an argument, run the program in ordinary mode.
public class BinarySearch{
    private int[] array;
    private BinarySearch(int[] array){
        //We have to use sorted array to perform binary search
        Arrays.sort(array);
        this.array = array;
    }
    //Recursive search
    private int searchUtilRecursive(int[] array, int start, int finish, int item){
        if((finish - start) == 1 && array[start] == item) return start;
        else if((finish - start) == 1 && array[start] != item) return -1;
        int middle = (finish - start)/2;
        if(array[start + middle] <= item) return searchUtilRecursive(array, start + middle, finish, item);
        else return searchUtilRecursive(array, start, start + middle, item);
    }
    //Ordinary search
    private int searchUtil(int[] array, int start, int finish, int item){
        start = (finish - start)/2;
        while((finish - start) >= 1){
            if(array[start] < item) start += (finish - start)/2;
            else finish = start;
            if((finish - start) == 1 && array[start] == item) return start;
            else if((finish - start) == 1 && array[start] == item) return -1;
        }
        return -1;
    }
    private int search(String mode, int item){
        switch(mode){
        case "R": System.out.println("Start test in Recursive mode"); 
            return searchUtilRecursive(array, 0, array.length, item);
        default: System.out.println("Start test in Ordinary mode");
            return searchUtil(array, 0, array.length, item);
        }
    }
    public static void main(String[] args){
        //The idea of the test is to examine log n time complexity.
        //We need to use large enough array to perform a search.
        //It helps us detect tiny distinctions between Java SE 
        //implementation and the custom search implementation.
        int numberOfRandoms = 10000000;
        int randomNumberToPick = new Random().nextInt(numberOfRandoms);
        IntStream intStream = new Random().ints();
        int[] intArray = intStream.limit(numberOfRandoms).toArray();
        BinarySearch binarySearch = new BinarySearch(intArray);

        Instant beforeInstantMyImpl = Instant.now();
        int resultMyImpl = binarySearch.search(args.length > 0 ? args[0] : "", intArray[randomNumberToPick]);
        Instant afterInstantMyImpl = Instant.now();

        Instant beforeInstantJavaImpl = Instant.now();
        int resultJavaImpl = Arrays.binarySearch(intArray, intArray[randomNumberToPick]);
        Instant afterInstantJavaImpl = Instant.now();

        assert resultMyImpl == resultJavaImpl: "Search result doesn't equal to Java SE implementation of search";
        assert beforeInstantMyImpl.until(afterInstantMyImpl, ChronoUnit.NANOS) == beforeInstantJavaImpl.until(afterInstantJavaImpl, ChronoUnit.NANOS): "Search is not as efficient as Java SE implementation";
        System.out.println("Test is passed");
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Your iterative implementation is incorrect, the recursive implementation is (significantly) slower than the iterative implementation of Arrays#binarySearch. \$\endgroup\$ – Nevay Oct 11 '17 at 13:52
2
\$\begingroup\$

Enhancing your benchmark

You might be able to enhance your benchmarks a little bit. Its generally worthwhile to run a test multiple times, as there are often other factors that will affect performance on your machine. This can include other programs running on your computer, available RAM/CPU to your process, etc. I find that I typically want to run something as many times as is reasonable within a given amount of time.

Once you've done that you'll have to find a reasonable metric to use; I typically go with the mean and also report on the standard error of the mean.

It's also often useful/interesting to compare performance at multiple problem sizes, but you might not be interested in that.

You'll also want to make sure that your benchmark actually takes long enough to run; I find that you at least want to be able to notice it pause to run. If that isn't the case here (I have no idea, I haven't run it) then add a few zeros at the end of numberOfRandoms. Eyeballing it, it looks like it should be fine as-is though.

One other thing to consider is that there is the possibility that you've loaded some of the values from the array into the cache, which can artificially enhance the performance of your second run. My general preferred strategy will look something like this:

repeat n times
    generate massive random array
    run version a
    do a ton of operations on a different massive array to make sure the cache is clean
    run version b
    kill cache again

My Java is rusty, but IIRC some of the newer versions allow higher order functions of some kind, in which case I'd write a function that performs the timing and cache clearing for you and takes a function as a parameter. If your version supports doing that I'd consider adding that as well.

Miscellaneous comments

You calculate the difference between finish and start multiple times in both searchUtilRecursive and searchUtil; just calculate it once at the top and then use that value.

Using a string to represent your mode in search is icky - make an enum.

Why are you sorting the array inside your BinarySearch constructor? Just pass it a sorted array. It's unexpected to me that if I call BinarySearch on an array that it will first sort it.

On that note, BinarySearch is weird to have as a class; I'd rather have your search functions be static functions (when do I ever want an instance of a BinarySearch?).

I really dislike that you have statements on the same lines as your if and else - these are small enough functions that it doesn't hurt you to put them on multiple lines, and its way more readable that way.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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