Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
binary search vs linear scan
package com.databricks.unsafe.util.benchmark;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@State(Scope.Benchmark)
public class BinarySearch {
@Param({"1", "10", "50", "100", "200", "250", "273", "365"})
public int dayInYear;
private static final int[] arr = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
@Benchmark
public long linearSearch() {
if (dayInYear <= 31) {
return 1;
} else if (dayInYear <= 59) {
return 2;
} else if (dayInYear <= 90) {
return 3;
} else if (dayInYear <= 120) {
return 4;
} else if (dayInYear <= 151) {
return 5;
} else if (dayInYear <= 181) {
return 6;
} else if (dayInYear <= 212) {
return 7;
} else if (dayInYear <= 243) {
return 8;
} else if (dayInYear <= 273) {
return 9;
} else if (dayInYear <= 304) {
return 10;
} else if (dayInYear <= 334) {
return 11;
} else {
return 12;
}
}
@Benchmark
public long binarySearch() {
int index = java.util.Arrays.binarySearch(arr, dayInYear);
return index > 0 ? index - 1 : - index - 2; // zero based
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(BinarySearch.class.getSimpleName())
.warmupIterations(5)
.measurementIterations(5)
.forks(2)
.jvmArgs("-ea")
.build();
new Runner(opt).run();
}
}
Benchmark (dayInYear) Mode Cnt Score Error Units
BinarySearch.binarySearch 1 thrpt 4 115347880.155 ± 8520914.477 ops/s
BinarySearch.binarySearch 10 thrpt 4 113654466.772 ± 8625273.222 ops/s
BinarySearch.binarySearch 50 thrpt 4 133030684.937 ± 10710487.122 ops/s
BinarySearch.binarySearch 100 thrpt 4 133953770.632 ± 12634401.850 ops/s
BinarySearch.binarySearch 200 thrpt 4 130781158.940 ± 8043762.686 ops/s
BinarySearch.binarySearch 250 thrpt 4 132553717.324 ± 21414919.596 ops/s
BinarySearch.binarySearch 273 thrpt 4 244471672.528 ± 9463128.602 ops/s
BinarySearch.binarySearch 365 thrpt 4 166535896.580 ± 28047392.033 ops/s
BinarySearch.linearSearch 1 thrpt 4 463719441.329 ± 106581527.249 ops/s
BinarySearch.linearSearch 10 thrpt 4 448299356.497 ± 166163742.716 ops/s
BinarySearch.linearSearch 50 thrpt 4 449009750.056 ± 113741145.284 ops/s
BinarySearch.linearSearch 100 thrpt 4 443775770.080 ± 31449395.157 ops/s
BinarySearch.linearSearch 200 thrpt 4 395199721.525 ± 28370833.771 ops/s
BinarySearch.linearSearch 250 thrpt 4 322339256.287 ± 153877281.219 ops/s
BinarySearch.linearSearch 273 thrpt 4 351028964.278 ± 34651113.649 ops/s
BinarySearch.linearSearch 365 thrpt 4 324125219.514 ± 33060425.949 ops/s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment