Skip to content

Instantly share code, notes, and snippets.

@milahu

milahu/index.html

Last active October 10, 2020 08:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save milahu/24ecbbbc5d760eb771f776b227d8c36b to your computer and use it in GitHub Desktop.
Save milahu/24ecbbbc5d760eb771f776b227d8c36b to your computer and use it in GitHub Desktop.
Download ZIP
binary search vs biased binary search (optimized for sequential search) #jsbench #jsperf (http://jsbench.github.io/#24ecbbbc5d760eb771f776b227d8c36b) #jsbench #jsperf
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>binary search vs biased binary search (optimized for sequential search) #jsbench #jsperf</title>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/1.0.0/benchmark.min.js"></script>
<script src="./suite.js"></script>
</head>
<body>
<h1>Open the console to view the results</h1>
<h2><code>cmd + alt + j</code> or <code>ctrl + alt + j</code></h2>
</body>
</html>
Raw
suite.js
"use strict";
(function (factory) {
if (typeof Benchmark !== "undefined") {
factory(Benchmark);
} else {
factory(require("benchmark"));
}
})(function (Benchmark) {
var suite = new Benchmark.Suite;
Benchmark.prototype.setup = function () {
const STEP_SIZE = () => 1+(Math.random()*10)|0;
// how sparse (not dense) are the input values?
// smaller values make biased search faster
const mappings = [];
for (let i = 0; i < 100; i++) {
const line = [];
for (let j = 0; j < 1000; j++) {
line.push([j, 0, i, j]); // output_column, source, line, column
}
mappings.push(line);
}
function binarySearch(haystack, needle, comparator) {
let low = 0;
let high = haystack.length - 1;
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp === 0) {
return mid;
}
if (cmp < 0) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1; // not found
}
function binarySearchBiased(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
for (let diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
}
else { // item < needle
low = state.last;
// find nearest high value
for (let diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFaster(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
for (let diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
high = low; // faster
}
}
else { // item < needle
low = state.last;
// find nearest high value
for (let diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
low = high; // faster
}
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOne(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
for (let diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
high = low - 1; // exclude low from range
}
}
else { // item < needle
low = state.last;
// find nearest high value
for (let diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
low = high + 1; // exclude high from range
}
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOneFasterExpand4(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
let diff;
for (diff = 1; ; diff *= 4) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
high = low + diff - 1;
if (high > max_high) high = max_high;
}
else { // item < needle
low = state.last;
// find nearest high value
let diff;
for (diff = 1; ; diff *= 4) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
low = high - diff + 1;
if (low < 0) low = 0;
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOneFaster(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
let diff;
for (diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
high = low + diff - 1;
}
else { // item < needle
low = state.last;
// find nearest high value
let diff;
for (diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
low = high - diff + 1;
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOneFasterExpand3(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
let diff;
for (diff = 1; ; diff *= 3) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
high = low + diff - 1;
if (high > max_high) high = max_high;
}
else { // item < needle
low = state.last;
// find nearest high value
let diff;
for (diff = 1; ; diff *= 3) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
low = high - diff + 1;
if (low < 0) low = 0;
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOneFasterExpandRandom(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
const rand = () => 2 + (Math.random()*3)|0; // 2 .... 5
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
let diff;
for (diff = 1; ; diff *= rand()) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
high = low + diff - 1;
if (high > max_high) high = max_high;
}
else { // item < needle
low = state.last;
// find nearest high value
let diff;
for (diff = 1; ; diff *= rand()) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
low = high - diff + 1;
if (low < 0) low = 0;
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function binarySearchBiasedFasterPlusOneFasterExpand4(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
let diff;
for (diff = 1; ; diff *= 4) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
}
high = low + diff - 1;
if (high > max_high) high = max_high;
}
else { // item < needle
low = state.last;
// find nearest high value
let diff;
for (diff = 1; ; diff *= 4) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
}
low = high - diff + 1;
if (low < 0) low = 0;
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function sortSegments(segments) {
segments.sort(segmentComparator);
}
function compareSegmentColumn(haystack_item, needle) {
return haystack_item[0] - needle;
}
};
suite.add("binary search", function () {
// binary search
for (let i = 0; i < 25; i++) {
const line = mappings[i];
for (let j = 0; j < 1000; j += STEP_SIZE()) {
binarySearch(line, j, compareSegmentColumn)
}
}
});
suite.add("biased binary search", function () {
// biased binary search
// optimized for sequential search
// = last result is similar to current result
search_state = { last: 0 };
for (let i = 0; i < 25; i++) {
const line = mappings[i];
for (let j = 0; j < 1000; j += STEP_SIZE()) {
binarySearchBiased(line, j, compareSegmentColumn, search_state)
}
}
});
suite.add("biased binary search - faster", function () {
// biased binary search - faster
// optimized for sequential search
// = last result is similar to current result
search_state = { last: 0 };
for (let i = 0; i < 25; i++) {
const line = mappings[i];
for (let j = 0; j < 1000; j += STEP_SIZE()) {
binarySearchBiasedFaster(line, j, compareSegmentColumn, search_state)
}
}
});
suite.add("biased binary search - faster plus one", function () {
// biased binary search - faster plus one
// optimized for sequential search
// = last result is similar to current result
search_state = { last: 0 };
for (let i = 0; i < 25; i++) {
const line = mappings[i];
for (let j = 0; j < 1000; j += STEP_SIZE()) {
binarySearchBiasedFasterPlusOne(line, j, compareSegmentColumn, search_state)
}
}
});
suite.on("cycle", function (evt) {
console.log(" - " + evt.target);
});
suite.on("complete", function (evt) {
console.log(new Array(30).join("-"));
var results = evt.currentTarget.sort(function (a, b) {
return b.hz - a.hz;
});
results.forEach(function (item) {
console.log((idx + 1) + ". " + item);
});
});
console.log("binary search vs biased binary search (optimized for sequential search) #jsbench #jsperf");
console.log(new Array(30).join("-"));
suite.run();
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment