OlognBenchmark

FindBenchmark.java

package com.test;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Thread)
@Fork(1)
@Warmup(iterations = 10, time = 1000, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.MILLISECONDS)
public class FindBenchmark {
    
    @Param({"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})
    public int inputSize;
    
    private double[] input;
    private double lookingFor;
    
    @Setup
    public void init() {
        input = new double[inputSize];
        Random rnd = new Random();
        for(int i = 0; i < inputSize; i++) {
            input[i] = rnd.nextDouble();
        }
        Arrays.sort(input);
        lookingFor = rnd.nextDouble();
    }
    
    @Benchmark
    public int testBinarySearch() {
        int low = 0;
        int high = input.length - 1;
        int mid = 0;

        while( low <= high )
        {
            mid = ( low + high ) / 2;
            if( input[ mid ] < lookingFor ) {
                low = mid + 1;
            } else if( input[ mid ] > lookingFor ) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        
        double midDist = Math.abs(input[mid] - lookingFor);
        if(mid > 1 && Math.abs(input[mid - 1] - lookingFor) < midDist) {
            return mid - 1;
        }
        if(mid < input.length - 1 && Math.abs(input[mid + 1] - lookingFor) < midDist) {
            return mid + 1;
        }
        return mid;
    }

    @Benchmark
    public int testIterSearch() {
        double distance = Double.MAX_VALUE;
        int found = -1;
        for( int i = 0; i < input.length; i++) {
            double d = Math.abs(input[i] - lookingFor);
            if(d < distance) {
                distance = d;
                found = i;
            }
        }
        return found;
    }

}