Skip to content

Instantly share code, notes, and snippets.

@amaembo
Created Sep 21, 2020
Embed
What would you like to do?
Comparison of linear and binary search in Java
package com.com.example;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.CompilerControl;
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;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
@Fork(3)
@Warmup(iterations = 5, time = 200, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 200, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
public class Search {
@Param({"1", "5", "10", "15", "20", "25", "30", "40", "50"})
private int size;
private int[] haystack;
int needle;
private int total;
@Setup
public void setup() {
haystack = new int[size];
for (int i = 0; i < haystack.length; i++) {
haystack[i] = i * 2;
}
total = size * 2 + 1;
}
@Benchmark
public int findBinarySearch() {
needle++;
if (needle == total) needle = 0;
return binarySearch(haystack, needle);
}
@CompilerControl(CompilerControl.Mode.DONT_INLINE)
private int binarySearch(int[] haystack, int needle) {
return Arrays.binarySearch(haystack, needle);
}
@Benchmark
public int findLinear() {
needle++;
if (needle == total) needle = 0;
return linearSearch(haystack, needle);
}
@CompilerControl(CompilerControl.Mode.DONT_INLINE)
private int linearSearch(int[] haystack, int needle) {
for (int i = 0; i < haystack.length; i++) {
int value = haystack[i];
if (value >= needle) {
return value == needle ? i : -i;
}
}
return -haystack.length;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment