Benchmark: Array.find vs. Map.get semua

Array.find vs. Map.get semua (version: 1)

Test the performance of Array.find vs. Map.get, with various array sizes, and with/without conversion from array to map

Comparing performance of: Array.find, 100 elements vs Map.get, 100 elements vs Array.find, 1 000 000 elements vs Map.get, 1 000 000 elements vs Array to Map + Map.get, 1 lookup vs Array to Map + Map.get, 10 lookups vs Array to Map + Map.get, 100 lookups vs Array.find, 10 lookups vs Array.find, 100 lookups

Created: 3 days ago by: Guest

Jump to the latest result

Script Preparation code:

function getRandomElement(id) {
  return {
    id,
    a: Math.random(),
    b: Math.random(),
    c: Math.random(),
  }
}

function getArray(length) {
  const result = [];
  for (let i = 0; i < length; i++) {
    result.push(getRandomElement(i))
  }
  
  return result;
}

function arrayToMap(array) {
  return new Map(array.map(el => [el.id, el]));
}

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

array_small = getArray(10000);
array_large = getArray(1000000);

map_small = arrayToMap(array_small);
map_large = arrayToMap(array_large);

Tests:

Array.find, 100 elements
const target = getRandomInt(99); array_small.find(el => el.id === target);
Map.get, 100 elements
const target = getRandomInt(99); map_small.get(target);
Array.find, 1 000 000 elements
const target = getRandomInt(999999); array_large.find(el => el.id === target);
Map.get, 1 000 000 elements
const target = getRandomInt(999999); map_large.get(target)
Array to Map + Map.get, 1 lookup
const map = arrayToMap(array_small); const target = getRandomInt(9999); map.get(target);
Array to Map + Map.get, 10 lookups
const map = arrayToMap(array_small); for (let i = 0; i < 10; i++) { const target = getRandomInt(9999); map.get(target); }
Array to Map + Map.get, 100 lookups
const map = arrayToMap(array_small); for (let i = 0; i < 100; i++) { const target = getRandomInt(9999); map.get(target); }
Array.find, 10 lookups
for (let i = 0; i < 10; i++) { const target = getRandomInt(9999); array_small.find(el => el.id === target) }
Array.find, 100 lookups
for (let i = 0; i < 100; i++) { const target = getRandomInt(9999); array_small.find(el => el.id === target) }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Array.find, 100 elements
Map.get, 100 elements
Array.find, 1 000 000 elements
Map.get, 1 000 000 elements
Array to Map + Map.get, 1 lookup
Array to Map + Map.get, 10 lookups
Array to Map + Map.get, 100 lookups
Array.find, 10 lookups
Array.find, 100 lookups

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 days ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36 OPR/114.0.0.0

Browser/OS: Opera 114 on Windows

View result in a separate tab

Test name	Executions per second
Array.find, 100 elements	11533207.0 Ops/sec
Map.get, 100 elements	59502740.0 Ops/sec
Array.find, 1 000 000 elements	261.2 Ops/sec
Map.get, 1 000 000 elements	57710892.0 Ops/sec
Array to Map + Map.get, 1 lookup	1589.0 Ops/sec
Array to Map + Map.get, 10 lookups	1606.7 Ops/sec
Array to Map + Map.get, 100 lookups	1711.6 Ops/sec
Array.find, 10 lookups	18282.5 Ops/sec
Array.find, 100 lookups	1682.9 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated 3 days ago):

LLMs can make mistakes. Check important info.

The benchmark defined on MeasureThat.net compares two different methods of searching for elements in collections in JavaScript: `Array.find()` and `Map.get()`. It aims to test the performance of these methods under varying conditions, such as the size of the collection and the conversion of an array into a map.

### Options Compared
1. **`Array.find()`**: 
   This method searches through an array for a condition and returns the first element that satisfies the provided testing function. The test cases vary in the number of lookups and the size of the array being searched.

2. **`Map.get()`**: 
   This method retrieves a value associated with the specified key from a `Map` instance. The benchmark measures how quickly values can be looked up following the creation of a map from an array.

### Pros and Cons
#### Array.find()
- **Pros**:
  - Simple and straightforward to use, especially for smaller collections or when needing to evaluate complex conditions.
  - No need for upfront transformation of data structures.
  
- **Cons**:
  - Linear time complexity (\(O(n)\)) in worst-case scenarios, meaning it can be inefficient for large arrays.
  - Performance degrades with the increase in the number of elements due to repeated scanning of the array.

#### Map.get()
- **Pros**:
  - Extremely fast lookups with constant time complexity (\(O(1)\)) on average, making it suitable for large datasets.
  - Ideal when you have many lookups for the same keys after an initial setup phase.

- **Cons**:
  - Requires an upfront conversion of an array to a `Map`, which adds overhead. This transformation itself has a time complexity of \(O(n)\).
  - Overhead may not be justified for smaller datasets or when the overhead of conversion outweighs the benefits of faster lookups.

### Other Considerations
- **Memory Usage**: `Map` generally consumes more memory than a simple array as it holds keys and values in a more complex structure. For small datasets or infrequent lookups, this might not be worthwhile.
- **Data Structure**: In applications where frequent searches are required, using a `Map` and performing a one-time transformation from an array can lead to significant performance gains. Conversely, for occasional searches or when the data is inherently small, using `Array.find()` could be more efficient.

### Library Usage
In this benchmark, the standard JavaScript objects and functions are used (`Array` and `Map`), both of which are part of the built-in JavaScript language, with no external libraries required.

### Special JavaScript Features
The benchmark doesn't employ any special JavaScript features or syntax. It strictly utilizes common language constructs (such as functions and data structures) that can be understood by anyone with a basic knowledge of JavaScript.

### Alternatives
1. **Linear Search**: Similar to `Array.find()` in functionality but implemented manually in loops, essentially using the same principles as `Array.find()` while enabling full control of the search logic.
  
2. **Binary Search**: If the dataset is sorted and doesn’t require frequent updates, utilizing binary search can minimize search time; however, this necessitates pre-sorting the data.

3. **Other data structures**: Depending on the use case, sorted arrays, trees, or hash tables could be more appropriate for specific types of data and access patterns.

In summary, this benchmark provides valuable insights into the performance characteristics of two common techniques used in JavaScript for searching elements in collections, demonstrating the trade-offs between ease of use and performance efficiency.

Related benchmarks:

Array.find vs. Map.get semua (version: 1)

Test the performance of Array.find vs. Map.get, with various array sizes, and with/without conversion from array to map

Created: 3 days ago by: Guest

Jump to the latest result

Array.find, 100 elements

Map.get, 100 elements

Array.find, 1 000 000 elements

Map.get, 1 000 000 elements

Array to Map + Map.get, 1 lookup

Array to Map + Map.get, 10 lookups

Array to Map + Map.get, 100 lookups

Array.find, 10 lookups

Array.find, 100 lookups

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated 3 days ago):