Benchmark: find range in array

Script Preparation code:

function randomIntFromInterval(min, max) { // min and max included 
  return Math.floor(Math.random() * (max - min + 1) + min)
}
var rows = [];
for(let i = 0; i<10000;i++) {
  rows.push(i * randomIntFromInterval(16,50));
}
function filterBinary(arr,min,max){
 var len   = arr.length
    ,up    = -1
    ,down  = len
    ,rrange= []
    ,mid   = Math.floor(len/2) 
 ;
 while (up++<mid && down-->mid){
    if (arr[up]>=max || arr[down]<=min){break;}
    if (arr[up]>=min){
      rrange.push(arr[up]);
    }
    if (arr[down]<=max){
      rrange.push(arr[down]);
    }
 }
 return rrange;   
}
  Array.prototype.sliceRange = function(min, max) {
    if (min > max) return this.sliceRange(max, min);
    var l = 0,
        r = this.length;
    rough: {
        while (l < r) {
            var m = ~~(l + (r - l) / 2);
            if (this[m] < min)
                l = m + 1;
            else if (this[m] > max)
                r = m;
            else
                break rough;
        }
        return [];
    }
    var lr = m,
        rl = m;
    while (l < lr) {
        m = ~~(l + (lr - l) / 2);
        if (this[m] < min)
            l = m + 1;
        else
            lr = m;
    }
    while (rl < r) {
        m = ~~(rl + (r - rl) / 2);
        if (this[m] > max)
            r = m;
        else
            rl = m + 1;
    }
    return this.slice(l, r);
}
  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;

    for (var i = start; i < end; i++) {
        value = dates[i];
        if (value < min) {
            continue;
        }
        if (value > max) {
            break;
        }
        subArray.push(value);
    }
    return subArray;
}

Tests:

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

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
filterBinary
sliceRange
getDatesBetweenRange

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 dive into the benchmarking analysis.

**Benchmark Overview**

The test case "find range in array" is measured by creating an array of 10,000 elements and defining three methods to filter or manipulate this array:

1. `filterBinary(rows, min, max)`: uses a binary search-like approach to find the indices of elements within a specified range.
2. `rows.sliceRange(min, max)`: uses a binary search-like approach to find the slice of the array within a specified range.
3. `getDatesBetweenRange(dates, min, max)`: is not directly related to arrays, but rather a function that finds dates within a specified range.

**Options Compared**

The two options being compared are:

1. `filterBinary(rows, 70000, 70400)`
2. `rows.sliceRange(70000, 70400)`

Both methods aim to find the elements in the array within the specified range (70000 to 70400). However, they employ different strategies:

* `filterBinary`: uses a binary search-like approach by iterating over the array and comparing each element with the minimum and maximum values. It also keeps track of two pointers (`up` and `down`) that move towards the center of the array.
* `sliceRange`: uses a binary search-like approach to find the indices of the first and last elements within the range. It then slices the array using these indices.

**Pros and Cons**

1. **filterBinary**
	* Pros:
		+ Simple and intuitive implementation
		+ Can handle large arrays efficiently
	* Cons:
		+ May not be as efficient for very small arrays or edge cases
		+ Requires extra memory to store the `up` and `down` pointers
2. **sliceRange**
	* Pros:
		+ More efficient for very small arrays or edge cases
		+ Only requires a single slice operation, reducing overhead
	* Cons:
		+ May not be as intuitive or straightforward implementation
		+ Requires more complex logic to handle edge cases

**Library Usage**

None of the provided methods use external libraries.

**Special JS Feature/Syntax**

The `sliceRange` method uses a non-standard property `Array.prototype.sliceRange`, which is not a part of the standard JavaScript API. This suggests that it may be a custom implementation or an experimental feature.

**Alternative Approaches**

Other approaches to find elements within a range in an array could include:

1. Using `map()` and filtering the resulting array
2. Using `forEach()` and iterating over the array manually
3. Using specialized algorithms like binary search with offset calculations

However, these alternatives may not be as efficient or straightforward as the `filterBinary` and `sliceRange` approaches.

**Conclusion**

The choice between `filterBinary` and `sliceRange` depends on the specific use case and requirements. If efficiency is a top priority for large arrays, `sliceRange` might be a better option. However, if simplicity and ease of implementation are more important, `filterBinary` could be a better fit.

Related benchmarks:

find range in array (version: 0)

Comparing performance of: filterBinary vs sliceRange vs getDatesBetweenRange

Created: 4 years ago by: Guest

Jump to the latest result

filterBinary

sliceRange

getDatesBetweenRange

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