Why is Arrays.binarySearch not improving the performance compared to walking the array?

Question

I gave a shot at solving the Hackerland Radio Transmitters programming challange.

To summarize, challenge goes as follows:

Hackerland is a one-dimensional city with n houses, where each house i is located at some x_i on the x-axis. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a range, k, meaning it can transmit a signal to all houses ≤ k units of distance away.

Given a map of Hackerland and the value of k, can you find the minimum number of transmitters needed to cover every house?

My implementation is as follows:

package biz.tugay;

import java.util.*;

public class HackerlandRadioTransmitters {

    public static int minNumOfTransmitters(int[] houseLocations, int transmitterRange) {
        // Sort and remove duplicates..
        houseLocations = uniqueHouseLocationsSorted(houseLocations);
        int towerCount = 0;
        for (int nextHouseNotCovered = 0; nextHouseNotCovered < houseLocations.length; ) {
            final int towerLocation = HackerlandRadioTransmitters.findNextTowerIndex(houseLocations, nextHouseNotCovered, transmitterRange);
            towerCount++;
            nextHouseNotCovered = HackerlandRadioTransmitters.nextHouseNotCoveredIndex(houseLocations, towerLocation, transmitterRange);
            if (nextHouseNotCovered == -1) {
                break;
            }
        }
        return towerCount;
    }

    public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
        final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
        final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
        int towerIndex = houseNotCoveredIndex;
        int loop = 0;
        while (true) {
            loop++;
            if (towerIndex == houseLocations.length - 1) {
                break;
            }
            if (farthestHouseLocationAllowed >= houseLocations[towerIndex + 1]) {
                towerIndex++;
                continue;
            }
            break;
        }
        System.out.println("findNextTowerIndex looped : " + loop);
        return towerIndex;
    }

    public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
        final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
        int notCoveredHouseIndex = towerIndex + 1;
        int loop = 0;
        while (notCoveredHouseIndex < houseLocations.length) {
            loop++;
            final int locationOfHouseBeingChecked = houseLocations[notCoveredHouseIndex];
            if (locationOfHouseBeingChecked > towerCoversUntil) {
                break; // Tower does not cover the house anymore, break the loop..
            }
            notCoveredHouseIndex++;
        }
        if (notCoveredHouseIndex == houseLocations.length) {
            notCoveredHouseIndex = -1;
        }
        System.out.println("nextHouseNotCoveredIndex looped : " + loop);
        return notCoveredHouseIndex;
    }

    public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
        Arrays.sort(houseLocations);
        final HashSet<Integer> integers = new HashSet<>();
        final int[] houseLocationsUnique = new int[houseLocations.length];

        int innerCounter = 0;
        for (int houseLocation : houseLocations) {
            if (integers.contains(houseLocation)) {
                continue;
            }
            houseLocationsUnique[innerCounter] = houseLocation;
            integers.add(houseLocationsUnique[innerCounter]);
            innerCounter++;
        }
        return Arrays.copyOf(houseLocationsUnique, innerCounter);
    }
}

I am pretty sure this implementation is correct. But please see the detail in the functions: findNextTowerIndex and nextHouseNotCoveredIndex: they walk the array one by one!

One of my tests is as follows:

static void test_01() throws FileNotFoundException {
    final long start = System.currentTimeMillis();
    final File file = new File("input.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
    final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381);
    assert minNumOfTransmitters == 1;
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds..");
}

where input.txt can be downloaded from here. (It is not the most important detail in this question, but still..) So we have an array of 73382 houses, and I deliberately set the transmitter range so the methods I have loop a lot:

Here is a sample output from this test in my machine:

findNextTowerIndex looped : 38213
nextHouseNotCoveredIndex looped : 13785
Took: 359 milliseconds..

I also have this test, which does not assert anything, but just keeps time:

static void test_02() throws FileNotFoundException {
    final long start = System.currentTimeMillis();
    for (int i = 0; i < 400; i ++) {
        final File file = new File("input.txt");
        final Scanner scanner = new Scanner(file);
        int[] houseLocations = new int[73382];
        for (int counter = 0; counter < 73382; counter++) {
            houseLocations[counter] = scanner.nextInt();
        }
        final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);

        final int transmitterRange = ThreadLocalRandom.current().nextInt(1, 70000);
        final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
    }
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds..");
}

where I randomly create 400 transmitter ranges, and run the program 400 times.. I will get run times as follows in my machine..

Took: 20149 milliseconds..

So now, I said, why don 't I use binary search instead of walking the array and changed my implementations as follows:

public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
    final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
    final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
    int nextTowerIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, farthestHouseLocationAllowed);

    if (nextTowerIndex < 0) {
        nextTowerIndex = -nextTowerIndex;
        nextTowerIndex = nextTowerIndex -2;
    }

    return nextTowerIndex;
}

public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
    final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
    int nextHouseNotCoveredIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, towerCoversUntil);

    if (-nextHouseNotCoveredIndex > houseLocations.length) {
        return -1;
    }

    if (nextHouseNotCoveredIndex < 0) {
        nextHouseNotCoveredIndex = - (nextHouseNotCoveredIndex + 1);
        return nextHouseNotCoveredIndex;
    }

    return nextHouseNotCoveredIndex + 1;
}

and I am expecting a great performance boost, as now I will at most loop for log(N) times, instead of O(N).. So test_01 outputs:

Took: 297 milliseconds..

Remember, it was Took: 359 milliseconds.. before. And for test_02:

Took: 18047 milliseconds..

So I always get values around 20 seconds with array walking implementation and 18 - 19 seconds for binary search implementation.

I was expecting a much better performance gain using Arrays.binarySearch but obviously it is not the case, why is this? What am I missing? Do I need an array with more than 73382 to see the benefit, or is it irrelevant?

Edit #01

After @huck_cussler 's comment, I tried doubling and tripling the dataset I have (with random numbers) and tried running test02 (of course with tripling the array sizes in the test itself..). For the linear implementation the times go like this:

Took: 18789 milliseconds..
Took: 34396 milliseconds..
Took: 53504 milliseconds..

For the binary search implementation, I got values as follows:

Took: 18644 milliseconds..
Took: 33831 milliseconds..
Took: 52886 milliseconds..

Budd

Testing two implementations at one size won't expose different big-Oh behaviors. What happens as you increase the problem size? That is where you should see that the time required for the linear solution will grow faster. The time required for a linear algorithm should roughly double each time the problem size doubles. – Airbrush

@huck_cussler I tried doubling the input I have and I the linear solution does not seem to grow faster as you suggested. I get values like 18789 - 34396 for the linear solution and 18644 - 33831 for the binary search solution for test2 when I double the input data.They both seem to increase like O(N).. – Budd

@huck_cussler Please see my edit.. – Budd

My first thought would be to move the line of code where you start the timer. If I understand the problem correctly, n is the number of houses which appears to be 73382 in your test code. Do you agree with that? Assuming that is the case, by putting the timer start at the beginning of the method you are capturing the for loop that runs n times. Even if that operation is relatively fast, it is still linear and will override your log(n) behavior. What happens if you move the timer start to after the for loop that runs 73382 times? ... – Airbrush

... This means you will have to stop the timer inside of the outer loop, which makes timing a bit more complicated. You'll have to either aggregate the run time over the 400 iterations, or (a better option in my opinion) do all of the set up separately, then time only the operations you are interested in. So, do all the stuff you do on lines 4-9 of test_02 somewhere else, then loop 400 times just doing the code that solves the problem. – Airbrush

Answer 1

Your timing includes the retrieval of data from your hard drive. This could be taking the majority of your runtime. Omit the data load from your timing to get a more accurate comparison of your two approaches. Imagine if it takes up 18 seconds and you're comparing 18.644 vs 18.789 (0.77% improvement) instead of 0.644 vs 0.789 (18.38% improvement).

If you have a linear operation O(n), such as loading a binary structure, and you combine it with a binary search O(log n), you end up with O(n). If you trust Big O notation, then you should expect O(n + log n) to not be significantly different from O(2 * n) as they both reduce to O(n).

Also, a binary search may perform better or worse than a linear search depending on the density of houses between towers. Consider, say 1024 homes with a tower evenly dispersed every 4 homes. A linear search will step 4 times per tower, while a binary search will take log2(1024)=10 steps per tower.

One more thing... your minNumOfTransmitters method is sorting the already-sorted array passed into it from test_01 and test_02. That resorting step takes longer than your searches themselves, which further obscures the timing differences between your two search algorithms.

======

I created a small timing class to give a better picture of what's happening. I've removed the line of code from minNumOfTransmitters to prevent it from rerunning the sort, and added a boolean param to select whether to use your binary version. It totals the sum of times for 400 iterations, separating out each step. The results on my system illustrate that the load time dwarfs the sort time, which in turn dwarfs the solve time.

  Load:  22.565s
  Sort:   4.518s
Linear:   0.012s
Binary:   0.003s

It's easy to see how optimizing that last step doesn't make much difference in overall runtime.

private static class Timing {
    public long load=0;
    public long sort=0;
    public long solve1=0;
    public long solve2=0;
    private String secs(long millis) {
        return String.format("%3d.%03ds", millis/1000, millis%1000);
    }
    public String toString() {
        return "  Load: " + secs(load) + "\n  Sort: " + secs(sort) + "\nLinear: " + secs(solve1) + "\nBinary: " + secs(solve2);
    }
    public void add(Timing timing) {
        load+=timing.load;
        sort+=timing.sort;
        solve1+=timing.solve1;
        solve2+=timing.solve2;
    }
}

static Timing test_01() throws FileNotFoundException {
    Timing timing=new Timing();
    long start = System.currentTimeMillis();
    final File file = new File("c:\\path\\to\\xnpwdiG3.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    timing.load+=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
    timing.sort=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, false);
    timing.solve1=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int minNumOfTransmittersBin = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, true);
    timing.solve2=System.currentTimeMillis()-start;
    final long end = System.currentTimeMillis();
    return timing;
}

Arciniega

Answer 2

In your time measurement you include operations that are much slower than array search. Namely filesystem I/O and array sorting. I/O in general (reading/writing from filesystem, network communication) is by orders of magnitude slower than operations that involve only CPU and RAM access.

Let's rewrite your test in a way that does not read the file on every loop iteration:

static void test_02() throws FileNotFoundException {
        final File file = new File("input.txt");
        final Scanner scanner = new Scanner(file);
        int[] houseLocations = new int[73382];
        for (int counter = 0; counter < 73382; counter++) {
            houseLocations[counter] = scanner.nextInt();
        }
        scanner.close();
        final int rounds = 400;
        final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);
        final int transmitterRange = 73381;
        final long start = System.currentTimeMillis();
        for (int i = 0; i < rounds; i++) {
            final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        }
        final long end = System.currentTimeMillis();
        System.out.println("Took: " + (end - start) + " milliseconds..");
}

Notice in this version of the test the file is read only once and time measuring starts after that. With the above, I get Took: 1700 milliseconds.. (more or less a few millis) for both the iterative version and the binary search. So we still can't see that binary search is faster. That's because almost all of that time goes into sorting the array 400 times.

Now let's remove the line that sorts the input array from the minNumOfTransmitters method. We sort the array (once) anyway at the beginning of the test.

Now we can see that things are much faster. After removing the line houseLocations = uniqueHouseLocationsSorted(houseLocations) from minNumOfTransmitters I get: Took: 68 milliseconds.. for the iterative version. Clearly, since this duration is already very small, we will not see a significant difference with the binary search version.

So let's increase the number of loop rounds to: 100000.
Now I get Took: 2121 milliseconds.. for the iterative version and Took: 36 milliseconds.. for the binary search version.

Because we now isolated what we measure and focus on the array searches, rather than including operations that are much slower, we can notice the big difference in performance (for the better) of binary search.

If you want to see how many times binary search enters its while loop, you can implement it yourself and add a counter:

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int loop = 0;
        while (low <= high) {
            loop++;
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }
        System.out.println("binary search looped " + loop + " times");
        return -(low + 1);  // key not found.
}

The method is copied from the Arrays class in the JDK - I just added the loop counter and the println.
When the length of the array to search is 73382, the loop enters only 16 times. That is exactly what we expect: log(73382) =~ 16.

Gospodin

I don't think that having fixed transmitterRange value of 73381 is a representative test for performance. – Orenorenburg

I fixed transmitterRange to 73381 because this is the worst case scenario, which means this gives the clearest demonstration of the difference in performance between iterative array search and binary search. That being said, staying with random transmitterRange still shows the binary search performs much better, albeit the difference between the versions is mitigated just a little bit. – Gospodin

I think this is actually a kind of best case scenario rather than worst case. – Orenorenburg

Answer 3

I agree with other answers that the main issue with your tests is that they measure wrong things: IO and sorting. But I don't think suggested tests are good. My suggestion is following:

static void test_02() throws FileNotFoundException {

    final File file = new File("43620487.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);


    final Random random = new Random(0); // fixed seed to have the same sequences in all tests
    long sum = 0;
    // warm up
    for (int i = 0; i < 100; i++) {
        final int transmitterRange = random.nextInt(70000) + 1;
        final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        sum += minNumOfTransmitters;
    }

    // actual measure
    final long start = System.currentTimeMillis();
    for (int i = 0; i < 4000; i++) {
        final int transmitterRange = random.nextInt(70000) + 1;
        final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        sum += minNumOfTransmitters;
    }
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds. Sum = " + sum);
}

Note also that I remove all System.out.println calls from findNextTowerIndex and nextHouseNotCoveredIndex and uniqueHouseLocationsSorted call from minNumOfTransmitters as they affect performance testing as well.

So what I think is important here:

1. Move all I/O and sorting out of the measurement loop
2. Perform some warm up outside of measurement
3. Use the same random sequence for all measurements
4. Don't dispose result of the calculation so JIT can't optimize that call out altogether

With such test I see about 10 times difference on my machine: around 80ms vs around 8ms.

And if you really want to do performance tests in Java you should consider using JMH aka Java Microbenchmark Harness

Orenorenburg

Answer 4

Agree with other answers, the IO time is most problem, and sort is second, the search is last time consumer.

And agree phatfingers's example, the binary search sometime is worst than linear search in your problem because totally linear search goes one loop for every element(n times compare) but binary search run for tower times (O(logn)*#tower)), one suggestion is that binary search not start from 0, but from current location

 int nextTowerIndex = Arrays.binarySearch(houseLocations, houseNotCoveredIndex+1, houseLocations.length, arthestHouseLocationAllowed)

then it should O(logn)*#tower/2) Even more, maybe you can calculate every tower cover how many houses avg then first compare avg houses then using binary search start from houseNotCoveredIndex + avg + 1, but not sure the performance is much better.

ps: sort and unique you can using TreeSet as

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
    final Set<Integer> integers = new TreeSet<>();

    for (int houseLocation : houseLocations) {
        integers.add(houseLocation);
    }
    int[] unique = new int[integers.size()];
    int i = 0;
    for(Integer loc : integers){
        unique[i] = loc;
        i++;
    }
    return unique;
}

Photosynthesis

Answer 5

uniqueHouseLocationsSorted is not efficient, andy solution seems better, but I think this could improve the time spent (note that I did not test the code):

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
    int size = houseLocations.length;

    if (size == 0)  return null; // you have to check for null later or maybe throw an exception here

    Arrays.sort(houseLocations);

    final int[] houseLocationsUnique = new int[size];

    int previous = houseLocationsUnique[0] = houseLocations[0];
    int innerCounter = 1;

    for (int i = 1; i < size; i++) {
        int houseLocation = houseLocations[i];

        if (houseLocation == previous) continue; // since elements are sorted this is faster

        previous = houseLocationsUnique[innerCounter++] = houseLocation;
    }

    return Arrays.copyOf(houseLocationsUnique, innerCounter);
}

Consider also using an Array list as copying the array takes time.

Beatabeaten