Benchmark: get with insert : Array vs Map 3

Script Preparation code:

function makeid(length) {
    var result           = '';
    var characters       = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
    var charactersLength = characters.length;
    for ( var i = 0; i < length; i++ ) {
      result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
   return result;
}


function newElt(isString) {
  return isString? makeid(50) : Math.round(Math.random() * Number.MAX_SAFE_INTEGER);
}

const numComparator = (a,b) => a - b;
const strComparator = (a,b) => a.localeCompare(b);

Array.lowerBound = function(array, element, comparator = element.substring? strComparator : numComparator) {
	let result = 0;
	let count = array.length; // Not n - 1
	let match = false;
	while (result < count) {
		const mid = Math.floor((result + count) / 2);
		const delta = comparator(element, array[mid]);
		if (delta <= 0) {
			count = mid;
			if (!delta) {
				match = true;
			}
		} else {
			result = mid + 1;
		}
	}
	if (match) {
		// search on the right if there is an element equals to elements
		match = result;
		do {
			if (element === array[match])
				return match;
		} while (++match<array.length && !comparator(element, array[match]));
	}
	return result;
};

Tests:

Array Num
let elts = new Array(); for(let i = 0; i<10000; ++i) { const elt = newElt(); let i = Array.lowerBound(elts, elt); if(i>=elts.length || elts[i] !== elt) { elts.splice(i, 0, elt); } }
Map Num
let elts = new Map(); for(let i = 0; i<10000; ++i) { const elt = newElt(); if(!elts.get(elt)) { elts.set(elt, elt); } }
Array Str
let elts = new Array(); for(let i = 0; i<10000; ++i) { const elt = newElt(true); let i = Array.lowerBound(elts, elt); if(i>=elts.length || elts[i] !== elt) { elts.splice(i, 0, elt); } }
Map Str
let elts = new Map(); for(let i = 0; i<10000; ++i) { const elt = newElt(true); if(!elts.get(elt)) { elts.set(elt, elt); } }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Array Num
Map Num
Array Str
Map Str

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's break down the benchmark and explain what's being tested.

**Benchmark Overview**

The benchmark compares the performance of two data structures: Array and Map, in three different scenarios: searching for an element (insertion) in a sorted array and map. The comparison is done by inserting 10,000 random elements into each data structure and then searching for these elements using the `lowerBound` method.

**Options Compared**

There are four test cases:

1. **Array Num**: Array with numeric values
2. **Map Num**: Map with numeric values
3. **Array Str**: Array with string values
4. **Map Str**: Map with string values

The options being compared are the performance of each data structure in terms of search time.

**Pros and Cons**

Here's a brief overview of the pros and cons of each option:

* **Array Num**:
	+ Pros: Fast lookup times (average O(log n) complexity)
	+ Cons: Requires manual sorting, which can be time-consuming
* **Map Num**:
	+ Pros: Fast lookup times (average O(1) complexity), eliminates need for manual sorting
	+ Cons: May require additional memory to store keys and values
* **Array Str**:
	+ Pros: Fast lookup times (average O(log n) complexity)
	+ Cons: Requires manual sorting, which can be time-consuming
* **Map Str**:
	+ Pros: Fast lookup times (average O(1) complexity), eliminates need for manual sorting
	+ Cons: May require additional memory to store keys and values

**Libraries and Features**

The benchmark uses the following libraries:

* `Array.lowerBound`: A custom implementation of the lower bound search algorithm.
* `Map.set` and `Map.get`: Built-in methods for setting and getting key-value pairs in a Map.

There are no special JavaScript features or syntax used in this benchmark.

**Other Considerations**

When choosing between an Array and a Map, consider the following factors:

* **Data structure**: If you need to store key-value pairs, use a Map. Otherwise, use an Array.
* **Performance**: Maps can offer faster lookup times than Arrays for large datasets.
* **Memory usage**: Maps may require more memory to store keys and values.

**Alternatives**

If you're looking for alternative data structures or search algorithms, consider the following options:

* **Sorted Set**: A data structure that combines the benefits of an Array and a Map, offering fast lookup times and automatic sorting.
* **Hash Table**: A data structure that uses hashing to store key-value pairs, offering fast lookup times and average O(1) complexity.

Keep in mind that these alternatives may have different trade-offs in terms of memory usage, performance, and implementation complexity.

Related benchmarks:

get with insert : Array vs Map 3 (version: 1)

Comparing performance of: Array Num vs Map Num vs Array Str vs Map Str

Created: 4 years ago by: Registered User

Jump to the latest result

Array Num

Map Num

Array Str

Map Str

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):