Can there be an algorithm faster than linear search?

Question

I have heard that there is no faster algorithm faster than linear search (for an unsorted array), but, when I run this algorithm (linear):

public static void search(int[] arr, int value){
    for(int i = 0; i < arr.length; i++){
        if(arr[i] == value) return;
    }
}

With a random array of length 1000000, the average time to find a value is 75ns, but with this algorithm:

public static void skipSearch(int[] arr, int value){
    for(int i = 0; i < arr.length; i+=2){
        if(arr[i] == value) return;
    }
    for(int i = 1; i < arr.length; i+=2){
        if(arr[i] == value) return;
    }
}

I get a shorter average, 68ns?

Edit: A lot of you are saying that I didn't do a proper benchmark and this was by fluke, but I ran these functions 1000000 times and got the average. And every time I ran the functions 1000000 times, I got 75-76ns for the first algorithm, and 67-69ns for the second algorithm.

I used java's System.nanoTime() to measure this.

Code:

int[] arr = new int[1000];
Random r = new Random();
for(int i = 0; i < arr.length; i++){
    arr[i] = r.nextInt();
}
int N = 1000000;
long startTime = System.nanoTime();
for(int i = 0; i < N; i++){
    search(arr, arr[(int) Math.floor(Math.random()*arr.length)]);
}
System.out.println("Average Time: "+(System.nanoTime()-startTime)/(float)N+"ns");
startTime = System.nanoTime();
for(int i = 0; i < N; i++){
    skipSearch(arr, arr[(int) Math.floor(Math.random()*arr.length)]);
}
System.out.println("Average Skip Search Time: "+(System.nanoTime()-startTime)/(float)N+"ns");

Answer 1

It's quite possible that, as your search() methods do not return anything, and there isn't any action inside the loops, the JIT compiler in your JVM optimizes the code - in other words, modifies the byte-code before loading it to JVM so that both your search() methods most probably do not do (almost) anything. Which is most significant, it probably also completely removes the loops. JIT optimization is pretty smart, it can identify a lot of situations when it is not needed to load any code into JVM (however the code is in the byte-code .class file).

Then you measure just random numbers - not the real time complexity of your methods.

Read e.g. how to make sure no jvm and compiler optimization occurs, apply it and run your benchmark again.

Also change your search() methods so they return the index - thus making the life for the optimizer harder. However, sometimes it's surprisingly difficult to create a code which is impossible to be optimized :) Turning off the optimization (as in the link above) is more reliable.

---

Generally it doesn't make sense to benchmark unoptimized code. However, in this case the OP wants to measure a theoretical algorithm. He wants to measure the real number of passes. He has to ensure that the loops are actually performed. That's why he should turn the optimization off.

The OP thought that what he had measured was the speed of the algorithm, while in fact the algorithm had not even had a chance to run at all. Turning the JIT optimization off in this particular case fixes the benchmark.

Answer 2

This is why we are not concerned about literally timing how long things take to execute and more how things grow in scale as the complexity of the inputs increases. Have a look at asymptotic runtime analysis:

https://en.wikipedia.org/wiki/Analysis_of_algorithms

Answer 3

what is statistics of value ? Most likely it's even values in your case. It's quite clear that for both cases complexity of algorith O(n) and O(n/2) + O(n/2) that is pretty much same - linear time

Answer 4

It's just by chance that it's "faster". What you are probably noticing is that your values appear more often on an even index, than on an odd index.

Answer 5

In theory, the time complexity of both algorithms are the same O(n). One speculation why skipSearch was faster when you ran it is that the element you were searching for happened to be located at an even index, therefore it will be found by the first loop, and in the worst case it would do half the number of iterations of linearSearch. In benchmarks like these you not only need to consider the size of the data, but also what the data looks like. Try searching for an element that doesn't exist, an element that exists at an even index, an element that exists at an odd index.

Also, even if that skipSearch performs better using proper benchmarks, it still only shaves off a few nanoseconds, so there's no significant increase, and it's not worth using it in practice.

Answer 6

One of the problems mentioned by someone was that you're using different indices for each algorithm. So, to fix this I reworked a bit of your code. Here's the code I have:

int[] arr = new int[1000];
Random r = new Random();
for(int i = 0; i < arr.length; i++){
    arr[i] = r.nextInt();
}
int N = 1000000;
List<Integer> indices = new ArrayList<Integer>();
for(int i = 0; i < N; i++){
    //indices.add((int) Math.floor(Math.random()*arr.length/2)*2); //even only
    indices.add((int) Math.floor(Math.random()*arr.length/2)*2+1); //odd only
    //indices.add((int) Math.floor(Math.random()*arr.length)); //normal
}

long startTime = System.nanoTime();
for(Integer i : indices)
{
    search(arr, arr[i]);
}
System.out.println("Average Time: "+(System.nanoTime()-startTime)/(float)N+"ns");

startTime = System.nanoTime();
for(Integer i : indices)
{
    skipSearch(arr, arr[i]);
}
System.out.println("Average Skip Search Time: "+(System.nanoTime()-startTime)/(float)N+"ns");
    

So you'll notice I made an ArrayList<Integer> to hold indices, and I provide three different ways of populating that array list - one with even numbers only, one with odd numbers only, and your original random method.

Running with even numbers only produces this output:

Average Time: 175.609ns

Average Skip Search Time: 100.64691ns

Running with odd numbers only produces this output:

Average Time: 178.05182ns

Average Skip Search Time: 263.82928ns

Running with your original random value produces this output:

Average Time: 175.95944ns

Average Skip Search Time: 181.20367ns

Each of these results makes sense.

When selecting even indices only, your skipSearch algorithm is O(n/2), so we're processing no more than half the indices. Normally we don't care about constant factors in time complexity, but if we're actually looking at the run-time, then it matters. We're literally cutting the problem in half in this case, so that's going to impact the execution time. And we see the real execution time is almost cut in half accordingly.

When selecting only odd indices, we see a much greater impact to execution time. This is to be expected, because we're processing no less than half the indices.

When the original random selection is used, we see skipSearch doing worse(as we expect). This is because, on average, we'll have an even number of even indices and odd indices. The even numbers will be found quickly, but the odd numbers will be found very slowly. The linear search will find index 3 early on, whereas the skipSearch processes roughly O(n/2) elements before it'll find index 3.

As to why your original code gives odd results, is up in the air as far as I'm concerned. It could be that the pseudo-random number generator slightly favors even numbers, it could be due to optimizations, it could be due to branch predictor madness. But it certainly wasn't comparing apples to apples by selecting random indices for both algorithms. Some of those things could still be affecting my results, but at least the two algorithms are trying to find the same numbers now.

Answer 7

Both algorithms are doing the same, which one is faster depends on the place, where the value, you are looking for, is placed so it is coincidence, which one is faster in the ONE specific case.

But the first one is better coding style anyway.

Answer 8

When people call linear search the "fastest search," it's a purely academic statement. It has nothing to do with benchmarks, but rather the Big O complexity of the search algorithm. To make this measurement useful, Big O only defines the worst case scenario for a given algorithm.

In the real world, data does not always adhere to the worst case scenario, so benchmarks will fluctuate for different data sets. In your example, there is a 7ns difference between the two algorithms. However, what would happen if your data looked like this:

linear_data = [..., value];
skip_search_data = [value, ...];

That 7ns difference would get a lot larger. For linear search, the complexity would be O(n) every time. For skip search it would be O(1) every time.

In the real world, the "fastest" algorithm isn't always the fastest. Sometimes, your dataset lends itself to a different algorithm.