Skip to content

Instantly share code, notes, and snippets.

@d4tocchini

d4tocchini/index.html

Last active August 2, 2017 05:02
Show Gist options
  • Save d4tocchini/bab89686622850413bb8d79a55a319da to your computer and use it in GitHub Desktop.
Save d4tocchini/bab89686622850413bb8d79a55a319da to your computer and use it in GitHub Desktop.
Download ZIP
binary search #jsbench #jsperf (https://jsbench.github.io/#bab89686622850413bb8d79a55a319da) #jsbench #jsperf
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>binary 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 () {
var BinarySearch = function (list, val) {
var from = 0, to = list.length, cursor = Math.floor(from + (to - from) / 2);
while (list[cursor] !== val) {
if (from == to) {
return -1;
} else {
if (list[cursor] > val) {
to = cursor;
} else /*if (list[cursor] < val)*/ {
from = cursor;
}
cursor = Math.floor(from + (to - from) / 2);
}
}
return cursor;
};
function BinarySearchBitshift3 (list, val) {
var min = 0;
var max = list.length;
max--;
while(true) // fall back to linear search, 11 seems to be a good threshold, but this depends on the uses comparator!! (here: ===)
{
if (min + 8 > max) break
var mid = (min + max) >> 1;
var dat = list[ mid ];
if ( val === dat ) return mid;
if( val > dat ) {
min = mid + 1;
} else {
max = mid - 1;
}
}
while (max >= min) {
if( val === list[max] ) return max;
max--
}
return -1;
};
var BinarySearchBitshift = function (list, val) {
var min = 0
, max = list.length-1
;
for(;;)
{
// fall back to linear search, 11 seems to be a good threshold, but this depends on the uses comparator!! (here: ===)
if ( min + 11 > max ) {
for(var i=min ; i<=max; i++ ) {
if( val === list[i] ) {
return i;
}
}
return -1;
}
var mid = (min + max) >> 1;
var dat = list[ mid ];
if ( val === dat ) {
return mid;
}
if( val > dat ) {
min = mid + 1;
} else {
max = mid - 1;
}
}
};
function gt(x,y) {return (y - x) >>> 31 }
var bounds = new Uint32Array(2)
var BinarySearchBitshift2 = function (list, val) {
var min = 0
, max = list.length-1
;
for(;;)
{
// fall back to linear search, 11 seems to be a good threshold, but this depends on the uses comparator!! (here: ===)
// fall back to linear search, 11 seems to be a good threshold, but this depends on the uses comparator!! (here: ===)
if ( min + 11 > max ) {
for(var i=min ; i<=max; i++ ) {
if( val === list[i] ) {
return i;
}
}
return -1;
}
var mid = (min + max) >> 1;
var dat = list[ mid ]
var v = dat - val
if (v===0) return mid
if (v >>> 31) {
max = mid - 1
}else {
min = mid + 1
}
}
};
// http://codereview.stackexchange.com/questions/1480/better-more-efficient-way-of-writing-this-javascript-binary-search
var stackexchange = function (arr, ele) {
var beginning = 0, end = arr.length,
target;
while (true) {
target = ((beginning + end) >> 1);
if ((target === end || target === beginning) && arr[target] !== ele) {
return -1;
}
if (arr[target] > ele) {
end = target;
} else if (arr[target] < ele) {
beginning = target;
} else {
return target;
}
}
};
function SEARCH (array, newItem) {
let insertIndex = -1
let minIndex = 0
let lastIndex = array.length - 1
let maxIndex = lastIndex
let i, item
while (insertIndex === -1) {
// bitshift right, `x >> 1` is equivalent to `Math.floor(x/2)`
i = ((maxIndex - minIndex + 1) >> 1) + minIndex
item = array[i]
if (newItem <= item) {
maxIndex = i
if (i === 0) return i
if (minIndex + 1 === maxIndex) return (newItem <= array[minIndex]) ? minIndex : i
}
else if (newItem > item) {
minIndex = i
if (i === lastIndex) return i
if (minIndex + 1 === maxIndex) return (newItem <= array[maxIndex]) ? maxIndex : maxIndex + 1
}
}
}
var data0 = [1];
var data1 = [1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 15, 65, 67, 98, 321, 651, 4000, 5000, 6000, 7000, 10000, 11000, 12000, 15000, 65000, 67000, 98000, 320001, 651000];
var data2 = [1, 2, 3, 4, 5, 6, 7, 435, 546, 765, 766, 7687, 345365];
var data3 = [];
for(var i=0;i<10000;i++) data3.push( i * i - i );
var l0 = {}, l1 ={}, l2={}, l3={};
for(var i=0,m=data1.length;i<m;i++) l1[ data1[i] ] = i;
for(var i=0,m=data2.length;i<m;i++) l2[ data2[i] ] = i;
for(var i=0,m=data3.length;i<m;i++) l3[ data3[i] ] = i;
typed0 = new Uint32Array(data0)
typed1 = new Uint32Array(data1)
typed2 = new Uint32Array(data2)
typed3 = new Uint32Array(data3)
};
suite.add("BinarySearchBitshift(data0, 0);", function () {
BinarySearchBitshift(data0, 0);
BinarySearchBitshift(data1, 1);
BinarySearchBitshift(data2, 546);
BinarySearchBitshift(data3, 1892);
BinarySearchBitshift(data3, 49999);
BinarySearchBitshift(data3, 4999);
});
suite.add("BinarySearchBitshift3(data0, 0);", function () {
BinarySearchBitshift3(data0, 0);
BinarySearchBitshift3(data1, 1);
BinarySearchBitshift3(data2, 546);
BinarySearchBitshift3(data3, 1892);
BinarySearchBitshift3(data3, 49999);
BinarySearchBitshift3(data3, 4999);
});
suite.add("BinarySearchBitshift(typed0, 0);", function () {
BinarySearchBitshift(typed0, 0);
BinarySearchBitshift(typed1, 1);
BinarySearchBitshift(typed2, 546);
BinarySearchBitshift(typed3, 1892);
BinarySearchBitshift(typed3, 49999);
BinarySearchBitshift(typed3, 4999);
});
suite.add("typed0.includes(0);", function () {
typed0.includes(0);
typed1.includes(1);
typed2.includes(546);
typed3.includes(1892);
typed3.includes(49999);
typed3.includes(4999);
});
suite.add("BinarySearchBitshift2(data0, 0);", function () {
BinarySearchBitshift2(data0, 0);
BinarySearchBitshift2(data1, 1);
BinarySearchBitshift2(data2, 546);
BinarySearchBitshift2(data3, 1892);
BinarySearchBitshift2(data3, 49999);
BinarySearchBitshift2(data3, 4999);
});
suite.add("BinarySearchBitshift2(typed0, 0);", function () {
BinarySearchBitshift2(typed0, 0);
BinarySearchBitshift2(typed1, 1);
BinarySearchBitshift2(typed2, 546);
BinarySearchBitshift2(typed3, 1892);
BinarySearchBitshift2(typed3, 49999);
BinarySearchBitshift2(typed3, 4999);
});
suite.add("data0.indexOf(0);", function () {
data0.indexOf(0);
data1.indexOf(1);
data2.indexOf(546);
data3.indexOf(1892);
data3.indexOf(49999);
data3.indexOf(4999);
});
suite.add("data0.includes(0);", function () {
data0.includes(0);
data1.includes(1);
data2.includes(546);
data3.includes(1892);
data3.includes(49999);
data3.includes(4999);
});
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 #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