Benchmark: find index range in array2

Script Preparation code:

function randomIntFromInterval(min, max) {
  // min and max included
  return Math.floor(Math.random() * (max - min + 1) + min);
}
var rows = [];
let lasth = 0;
for (let i = 0; i < 10000; i++) {
  lasth += randomIntFromInterval(16, 50);
  rows.push(lasth);
}

function sliceRange(arr, min, max) {
  var l = 0,
    r = arr.length, res = [];
  rough: {
    while (l < r) {
      var m = ~~(l + (r - l) / 2);
      if (arr[m] < min) l = m + 1;
      else if (arr[m] > max) r = m;
      else break rough;
    }
    return [];
  }
  var lr = m,
    rl = m;
  while (l < lr) {
    m = ~~(l + (lr - l) / 2);
    if (arr[m] < min) l = m + 1;
    else lr = m;
  }
  while (rl < r) {
    m = ~~(rl + (r - rl) / 2);
    if (arr[m] > max) r = m;
    else rl = m + 1;
  }
    for (let i = 0; i < 60; i += 1) {
    const rid = i + l;
    if (rid < arr.length) res.push(rid);
  }
  return res;
}
function getDatesBetweenRange(dates, min, max) {
  var subArray = [];
  var value, iCntr;
  var start, end;

  var low = 0,
    high = dates.length - 1;
  while (high - low > 1) {
    centre = Math.floor((high + low) / 2);
    if (dates[centre] < min) low = centre;
    else high = centre;
  }
  start = low;
  high = dates.length - 1;
  while (high - low > 1) {
    centre = Math.floor((high + low) / 2);
    if (dates[centre] > max) high = centre;
    else low = centre;
  }
  end = high;
  return [start-1,end+1];
}

Tests:

sliceRange
sliceRange(rows, 70000, 70400)
getDatesBetweenRange
getDatesBetweenRange(rows, 70000, 70400)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
sliceRange
getDatesBetweenRange

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

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

Browser/OS: Chrome 98 on Windows

View result in a separate tab

Test name	Executions per second
sliceRange	1967762.9 Ops/sec
getDatesBetweenRange	55486.7 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's dive into the provided JSON data to understand what is being tested.

**Benchmark Definition**

The benchmark definition represents a JavaScript function that takes an array, and two bounds as input, and returns an array of indices within the original array that fall within the given range. In this case, we have two functions:

1. `sliceRange(arr, min, max)`: This function is designed to return all indices in the array `arr` that are greater than or equal to `min` and less than or equal to `max`.
2. `getDatesBetweenRange(dates, min, max)`: This function seems to be related to finding dates within a range, but it's not directly clear what its purpose is without more context.

**Options Compared**

The benchmark compares the execution performance of these two functions across different browsers and devices.

**Approaches Compared**

There are two main approaches being compared:

1. **Linear search**: Both `sliceRange` and `getDatesBetweenRange` use a binary search approach to find indices within a range. However, their implementation details differ.
2. **Approximation**: The `sliceRange` function uses an approximation technique called "rough" (explained later) to estimate the number of elements in the array that fall within the given range.

**Pros and Cons**

1. **Linear search**: While this approach is straightforward, it has a time complexity of O(n), making it less efficient for large arrays.
2. **Approximation (sliceRange)**: This approach uses the "rough" technique to estimate the number of elements in the array that fall within the given range. The pros include faster execution times and reduced memory usage. However, the cons include potential inaccuracies if the estimation is not correct.

**Rough Technique**

The "rough" technique is an optimization used in the `sliceRange` function to quickly estimate the number of elements in the array that fall within the given range. It works by:

1. Finding the first element greater than or equal to `min`.
2. Finding the last element less than or equal to `max`.
3. Counting the number of elements between these two indices.

This approach is faster but may not always provide accurate results.

**Library Used**

There doesn't appear to be any external libraries used in this benchmark.

**Special JS Features/Syntax**

The benchmark uses some JavaScript features and syntax, such as:

* `Math.floor` to round down a number.
* `Math.random` to generate random numbers.
* Template literals (`\r\n`) for formatting code.
* The "rough" technique is a custom optimization that is not part of the standard JavaScript library.

**Alternatives**

If you were to rewrite this benchmark, you could consider alternative approaches such as:

1. **Hashing**: Using a hash function (e.g., `Array.prototype.indexOf`) to quickly find elements within a range.
2. **Spatial indexing**: Using spatial indexing data structures (e.g., k-d trees) to efficiently search for elements within a range.

Keep in mind that these alternatives may require additional libraries or infrastructure, and their implementation would depend on the specific requirements of your use case.

Related benchmarks:

find index range in array2 (version: 0)

Comparing performance of: sliceRange vs getDatesBetweenRange

Created: 2 years ago by: Guest

Jump to the latest result

sliceRange

getDatesBetweenRange

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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