Benchmark: get with insert : Array vs Map

Script Preparation code:

function newPath() {
  return {
    id:Math.random() * Number.MAX_SAFE_INTEGER
  }
}

Array.lowerBound = function(array, element, comparator = (a,b) => a.id - b.id) {
	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
let paths = new Array(); for(let i = 0; i<10000; ++i) { const path = newPath(); let i = Array.lowerBound(paths, path); if(i>=paths.length || paths[i].id !== path.id) { paths.splice(i, 0, path); } }
Map
let paths = new Map(); for(let i = 0; i<10000; ++i) { const path = newPath(); let p = paths.get(path.id); if(!p) { paths.set(path.id, p); } }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Array
Map

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 is designed to compare the performance of two data structures: Arrays and Maps in JavaScript. The test case, titled "get with insert : Array vs Map", measures how fast it can find a specific element (in this case, an object created by the `newPath()` function) within the respective data structure.

**Options Compared**

The benchmark compares two options:

1. **Array**: Using the `lowerBound` method on an array to find the index of a specific element.
2. **Map**: Using the `get()` method on a Map to retrieve a value associated with a given key (in this case, the object's `id` property).

**Pros and Cons**

Here are some pros and cons of each approach:

* **Array (lowerBound)**:
	+ Pros: Arrays can be more efficient for large datasets since they don't require additional memory allocation for key-value pairs.
	+ Cons: The `lowerBound` method has a time complexity of O(log n), which may not be as efficient as Maps for very large datasets or when the number of unique keys is small.
* **Map**:
	+ Pros: Maps provide faster lookups (O(1) average case) and are more memory-efficient since they only store key-value pairs, making them suitable for large datasets with many unique keys.
	+ Cons: The `get()` method may incur additional overhead due to the lookup process.

**Library Usage**

In this benchmark, both Arrays and Maps use their built-in methods:

* `Array.lowerBound()`: a custom implementation of binary search for arrays.
* `Map.get()`: a standard JavaScript method for retrieving values from a Map.

**Special JS Feature/Syntax**

There are no special JavaScript features or syntax used in this benchmark that would require additional explanation.

**Alternatives**

Other alternatives to Arrays and Maps could be:

* Linked Lists: an ordered sequence of nodes, each containing data and a reference to the next node.
* Hash Tables: a data structure that maps keys to values using a hash function.
* Dictionaries: similar to Maps, but may have additional features or optimizations.

Keep in mind that this benchmark is designed to compare the performance of two specific data structures (Arrays and Maps) under a particular use case. The results might vary depending on the actual dataset size, complexity, and other factors not considered in this benchmark.

Related benchmarks:

get with insert : Array vs Map (version: 0)

Comparing performance of: Array vs Map

Created: 4 years ago by: Guest

Jump to the latest result

Array

Map

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):