Lodash：基于最小差值过滤大数组的最快实现方式问询

Hey there! Let's tackle this problem efficiently—especially critical when dealing with arrays as large as 100,000 elements. Your core requirements are clear: filter elements so consecutive kept items are at least delta apart, remove duplicates, and always retain the original array's minimum and maximum values.

Why Your Current orderBy + reduce Might Lag #

While higher-order functions like reduce are clean and readable, they add tiny per-iteration overhead that piles up for massive arrays. Plus, if you're sorting before deduplicating, you're wasting cycles sorting duplicate values—we can fix that to squeeze out more speed.

Optimal Approach (O(n log n) Time, Minimal Overhead) #

The fastest solution combines three optimized steps, leveraging native JS features for maximum performance:

1. Deduplicate first using a Set (far faster than manual deduplication loops).
2. Sort unique values with the engine-optimized native sort (no need to reinvent the wheel here).
3. Linear scan to filter with a plain for loop (avoids callback overhead from reduce).

Code Implementation #

function filterByMinDelta(arr, delta) {
    // Step 1: Deduplicate and sort (Set is nearly O(n), native sort is optimized O(n log n))
    const sortedUnique = [...new Set(arr)].sort((a, b) => a - b);
    const length = sortedUnique.length;

    // Edge cases: empty array or single element
    if (length <= 1) return sortedUnique;

    const result = [sortedUnique[0]]; // Start with the minimum value
    let currentThreshold = sortedUnique[0];

    // Step 2: Linear scan to pick elements meeting the delta requirement
    // Skip first (already added) and last (we'll add it later to guarantee inclusion)
    for (let i = 1; i < length - 1; i++) {
        const num = sortedUnique[i];
        if (num - currentThreshold >= delta) {
            result.push(num);
            currentThreshold = num;
        }
    }

    // Step 3: Ensure the maximum value is always included (even if it doesn't meet delta)
    const maxVal = sortedUnique[length - 1];
    if (maxVal !== result[result.length - 1]) {
        result.push(maxVal);
    }

    return result;
}

// Test your examples
console.log(filterByMinDelta([1,2,5,6,3,4,3,3,2,2], 3)); // Output: [1,4,6]
console.log(filterByMinDelta([1,2,3,4,5,6,7,8,9,10], 2)); // Output: [1,3,5,7,9,10]

Performance Breakdown #

• Deduplication: Set operations are average O(1) per element, making this step nearly linear time. Deduplicating first reduces the number of elements we need to sort—a massive win for arrays with lots of duplicates.
• Sorting: JavaScript engines (like V8 in Chrome/Node.js) use highly optimized sorting algorithms (Timsort for arrays over 22 elements), which is way faster than any custom sort you could write.
• Linear Filter: A plain for loop avoids the function call overhead of reduce, making this step as fast as possible for large arrays.

Edge Cases Handled #

• Empty array returns empty.
• Single-element array returns the element.
• All duplicate elements return a single-element array.
• Maximum value is always included, even if it's within delta of the last filtered element (like your second example where 10 is added after 9, even though 10-9=1 < 2).

内容的提问来源于stack exchange，提问作者Pumpkin Pie