is as fast as binary search. We will produce a
large number of random key value-pairs, perform a lookup to find a key with
and compare the performance. The key-value-pair array is used in json format. By the way we want to find
out if Array.sort is as fast as a javascript implementation of the quick sort algorithm.
In cases where client calculation time is crucial, the fastest way to retrieve an item of an
unsorted array is useful.
At first we will produce an array with 1.000.000 random key value pairs, e.g. [{key:234, value:"v218921"}].
For the random numbers we choose a range from 1 to 1.000.000.000.
In some cases, the procedure that ran as second item was faster than the first one.
In the longer run, the native Array.sort method seems to be slightly faster than a
quick sort implementation. With regard to the effort (additional code for qs) one
should use the native sort function.
In the next step we want to retrieve a key-value-pair from the array.
At first we start to find a value in the unsorted array with a normal loop O(n).
4.
Now we want to compare this to the time needed to find an item via Array.filter
5.
And finally we want to know whether a binary search in the sorted array is faster than the
Array.filter method.
We have add the time needed to sort the array + the time needed to binary find the item!
6.
Yes, Array.filter is faster as binary search. BUT: A simple loop is even faster than both.
Array.filter has to loop all the data, because it can retrieve multiple values as a result.
As binary search includes the sorting first, wich takes most of the time, this combination is too slow.
<script>
var items = [];
var items_ordered = [];
var lookup_key = 0;
var items_cnt = 1e6;
var random_max = 1e9;
var n = 10;
function createRandomKVPs() {
items = [];
var start = new Date().getTime();
for (i = 1; i < items_cnt; i++) {
var k = getRandomInt(1, random_max);
var v = ("v" + getRandomInt(1, random_max));
items.push({ 'key': k, 'value': v });
}
lookup_key = items[getRandomInt(1, items_cnt)];
var end = new Date().getTime();
var d = (end - start);
$('#status-create-rkvp').html('Status: OK, this took ' + d +
' milliseconds.');
}
function find_loop() {
var start = new Date().getTime();
for (var f = 0; f < items_cnt; f++) {
if (items[f].key == lookup_key.key) break;
}
var end = new Date().getTime();
var d = (end - start);
$('#status-find-loop').html('Status: OK, this took ' + d +
' milliseconds (' + f + ' loops).');
console.log(items[f].value + " / loops: " + f);
}
function find_filter() {
var start = new Date().getTime();
var result = items.filter(function (obj) {
return obj.key == lookup_key.key;
});
var end = new Date().getTime();
var d = (end - start);
$('#status-find-filter').html('Status: OK, this took ' + d +
' milliseconds.');
console.log(result[0].value);
}
function find_bin() {
var start = new Date().getTime();
sort();
var found_item = binarySearch(items, lookup_key);
var end = new Date().getTime();
var d = (end - start);
$('#status-find-bin').html('Status: OK, this took ' + d +
' milliseconds.');
console.log(found_item.value);
}
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function sort() {
items.sort(function (a, b) {
return a.key == b.key ? 0 :
a.key > b.key ? 1 : -1;
});
return true;
}
function sort1(debug) {
var items_ordered1 = items.slice();
var start = new Date().getTime();
items_ordered1.sort(function (a, b) {
return a.key == b.key ? 0 :
a.key > b.key ? 1 : -1;
});
var end = new Date().getTime();
var d = (end - start);
$('#status-sort1').html('Status: OK, this took ' + d +
' milliseconds');
//console.log(items);
//console.log(items_ordered1);
//if (debug) for (i = 0; i < 10; i++) { console.log(items_ordered1[i].key) };
return d;
}
function sort2(debug) {
var items_ordered2 = items.slice();
var start = new Date().getTime();
//quickSort(items_ordered2, 0, items_ordered2.length - 1)
quick_sort(items_ordered2, "key");
var end = new Date().getTime();
var d = (end - start);
$('#status-sort2').html('Status: OK, this took ' + d +
' milliseconds');
//console.log(items);
//console.log(items_ordered2);
//if (debug) for (i = 0; i < 10; i++) { console.log(items_ordered2[i].key) };
return d;
}
function sort1_perf() {
$('#status-sort1').html($('#status-sort1').html() +
' / average of ' + n + ' runs (' + averagePerformance(sort1, n) + ')');
}
function sort2_perf() {
$('#status-sort2').html($('#status-sort2').html() +
' / average of ' + n + ' runs (' + averagePerformance(sort2, n) + ')');
}
//https://gist.github.com/pedrombafonso/5668956
function partition(list, prop, begin, end, pivot) {
var piv = list[pivot];
swap(list, pivot, end - 1);
var store = begin;
var ix;
for (ix = begin; ix < end - 1; ++ix) {
if (list[ix][prop] <= piv[prop]) {
swap(list, store, ix);
++store;
}
}
swap(list, end - 1, store);
return store;
}
function swap(obj, a, b) {
var tmp = obj[a];
obj[a] = obj[b];
obj[b] = tmp;
}
function qsort(list, prop, begin, end) {
if (end - 1 > begin) {
var pivot = begin + Math.floor(Math.random() * (end - begin));
pivot = partition(list, prop, begin, end, pivot);
qsort(list, prop, begin, pivot);
qsort(list, prop, pivot + 1, end);
}
}
function quick_sort(list, prop) {
qsort(list, prop, 0, list.length);
}
function averagePerformance(proc, times) {
var start = new Date().getTime();
var d = 0;
for (var i = 0; i < times; i++) {
proc();
//console.log(proc());
}
var end = new Date().getTime();
var d = (end - start) / times;
return d;
}
//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
// DN: modified to handle JSON arrray
function binarySearch(items, value) {
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex) / 2);
while (items[middle].key != value.key && startIndex < stopIndex) {
//adjust search area
if (value.key < items[middle].key) {
stopIndex = middle - 1;
} else if (value.key > items[middle].key) {
startIndex = middle + 1;
}
//recalculate middle
middle = Math.floor((stopIndex + startIndex) / 2);
}
//make sure it's the right value
return (items[middle].key != value.key) ? -1 : items[middle];
}
</script>
