Empirical analysis for binary search not matching Theoretical Analysis

Question

I'm currently doing a test for the Binary searches average case. Simply all I do is I generate a random variable and then search for this random variable in different sized arrays using the binary search. Below is my code used:

   public static void main(String[] args) 
    {
        //This array keeps track of the times of the linear search
        long[] ArrayTimeTaken = new long[18];

        //Values of the array lengths that we test for
        int[] ArrayAssignValues = new int[18];
        ArrayAssignValues[0] = 1000000;
        ArrayAssignValues[1] = 10000000;
        ArrayAssignValues[2] = 20000000;
        ArrayAssignValues[3] = 30000000;
        ArrayAssignValues[4] = 40000000;
        ArrayAssignValues[5] = 50000000;
        ArrayAssignValues[6] = 60000000;
        ArrayAssignValues[7] = 70000000;
        ArrayAssignValues[8] = 80000000;
        ArrayAssignValues[9] = 90000000;
        ArrayAssignValues[10] = 100000000;
        ArrayAssignValues[11] = 110000000;
        ArrayAssignValues[12] = 120000000;
        ArrayAssignValues[13] = 130000000;
        ArrayAssignValues[14] = 140000000;
        ArrayAssignValues[15] = 150000000;
        ArrayAssignValues[16] = 160000000;
        ArrayAssignValues[17] = 170000000;

        //Code that runs the linear search
        for (int i = 0; i < ArrayAssignValues.length; i++) 
        {
            float[] arrayExperimentTest = new float[ ArrayAssignValues[i]];

            //We fill the array with ascending numbers 
            for (int j = 0; j < arrayExperimentTest.length; j++) 
            {
                arrayExperimentTest[j] = j;
            }

            Random Generator = new Random();
            int ValuetoSearchfor = (int) Generator.nextInt(ArrayAssignValues[i]);
            System.out.println(ValuetoSearchfor);
            ValuetoSearchfor = (int) arrayExperimentTest[ValuetoSearchfor];

            //Here we perform a the Linear Search
            ArrayTimeTaken[i] = BinarySearch(arrayExperimentTest,ValuetoSearchfor);
        }
        ChartCreate(ArrayTimeTaken);  
        System.out.println("Done");
    }

Here is my code for the binary search:

 static long BinarySearch(float[] ArraySearch,int ValueFind)
    {
        System.gc();
        long startTime = System.nanoTime();

        int low = 0;
        int high = ArraySearch.length-1;
        int mid = Math.round((low+high)/2);

        while (ArraySearch[mid] != ValueFind ) 
        {            
            if (ValueFind <ArraySearch[mid]) 
            {
                high = mid-1;
            }
            else
            {
                low = mid+1;
            }
            mid = (low+high)/2;
        }
        long TimeTaken = System.nanoTime() - startTime;
        return TimeTaken;
    }

Now the problem is that the results aren't making sense. Below is a graph:

enter image description here

Can some explain how the 1st array takes so much time? I've run the code a good few times and its basically the same graph created every time. Does Java some how cache results? Can anyone explain the result why the 1st binary search takes so long relativve to the others even though the array size is tiny compared to the rest?

Possibly the algo is running while parts of the JVM are loading up? JVM does do some lazy initialization under the covers. — Taylor, Aug 13 '13 at 19:37

score 2 · Accepted Answer · edited May 23 '17 at 12:23

It looks like you're doing these searches one after another, starting with the lowest values. If that's true, then the code will be running much slower, because the JIT compiler won't have had a chance to warm up yet. Generally, for benchmarking like this, you want to run through all relevant code to give the JIT compiler time to compile it and optimize before you do the real testing.

For more information on the JIT compiler, read this

You should also see this question to learn more about benchmarking.

Another possible cause of the slowness is that the JVM could still be in the process of starting up, and running it' own background code while you're timing it, causing slowdown.

score 1 · Answer 2 · edited May 23 '17 at 12:23

1

Benchmarking is not done this way, you should run at least 1000 cycles as a "warmup" and only then start measuring. Benchmarking could be more complicated than it seems, it should be carefully constructed to not be affected by other programs that run in the memory at the same time etc. Here and here you can find some good tips.

edited May 23 '17 at 12:23

Community

1
1

answered Aug 13 '13 at 19:40

Nir Alfasi

53,191
11
86
129

Empirical analysis for binary search not matching Theoretical Analysis

2 Answers2