Array vs SortedArray indexOf

Benchmark created on July 31, 2024

Setup

var count = 100000;

function createSortedNumberArray() {
	return new Proxy([], sorted_number_array_proxy_handler);
}
var sorted_number_array_proxy_handler = {
	get(target, prop, receiver) {
		switch(prop) {
			case "data": return target;
			case "add": return add;
			case "removeAt": return removeAt;
			case "removeFirst": return removeFirst;
			case "removeAll": return removeAll;
			case "indexOf": return indexOf;
			default:
				if (prop in target) { return target[prop]; }
				else { return Reflect.get(...arguments); }
		}
	},
	set(target, prop, value, receiver) {
	    return Reflect.get(...arguments);		
	}
};
function add(...values) {
	var data = this.data;
	for (var i = 0, value = values[i]; i < values.length; i++) {
		if (typeof value !== "number") { throw `Trying to add ${typeof value} to SortedNumberArray; can only add numbers.`; }
		
		if (data.length === 0) {
			data.push(value);
		}
		else if (data.length === 1) {
			if (value < data[0]) { data.unshift(value); }
			else { data.push(value); }
		}
		else if (value >= this.last) {
			data.push(value);
		}
		else if (value <= this.first) {
			data.unshift(value);
		}
		else { // value goes in the middle
			var index = find_nearest_index(value, data);
			data.splice(index,0, value);
		}
	}
}
function indexOf(value) {
	var data = this.data;
	var index = find_nearest_index(value, data);
	if (data[index] === value) { return index; }
	else { return -1; }
}

function removeAt(index) {
	this.data.splice(index,1);
	return this;
}
function removeFirst(value) {
	var index = this.indexOf(value);
	if (index !== -1) { this.removeAt(index); }
	return this;
}
function removeAll(value) {
	var index = this.indexOf(value);
	
}
function guess_index(value, from, from_index, to, to_index) {
	return from_index + (guess_progress(value, from, to) * (to_index - from_index)) | 0;
}
function guess_progress(value, from, to) {
	return (value-from) / (to-from);
}

var early_index, late_index;
function find_nearest_index(value, array) {
	early_index = 0; late_index = array.length - 1;
	do {
		var guessed_index = guess_index(value, array[early_index], early_index, array[late_index], late_index);
		var guess = array[guessed_index];
		if (guess === value) { return guessed_index; }
		else if (guessed_index <= early_index) { return early_index; }
		else if (guessed_index >= late_index) { return late_index + 1; }
		else if (value > guess) { early_index = guessed_index; }
		else if (value < guess) { late_index = guessed_index; }
	} while (early_index + 1 < late_index);

	return late_index;
}




var array = [];
var sorted_array = createSortedNumberArray();

for (var i = 0; i < count; i++) {
	var r = (Math.random() * 1000000) | 0;
	array.push(r); sorted_array.add(r);
}

Test runner

var index = (count * Math.random()) | 0;
sorted_array.indexOf(array[index]);

var index = (count * Math.random()) | 0;
array.indexOf(array[index]);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on July 31, 2024