JavaScript数组中范围内的值

Question

我有一个按升序排列的数组，在 JavaScript 中，其中包含以毫秒为单位的日期。

// Sample data; This may grow upto 1k or 2k
var dates = [1333391400000,1335292200000,1335810600000,1336329000000,1336933800000,1337020200000,
1337193000000,1337538600000,1337625000000,1337797800000,1338316200000,1338921000000,
1339093800000,1339439400000,1340303400000,1341772200000,1342463400000,1343068200000];

我没有开始和结束索引，而是有值。我需要从JavaScript数组中获取在两个日期（最小值和最大值）之间的所有日期。我通过JSON从Java获取此数组。

以下是获取最小值和最大值之间日期的方法：

function getDatesBetweenRange(min,max){
    var subArray = [];
    var value, jCntr=0;
    for(var iCntr=0;iCntr<dates.length;iCntr++){
         value = dates[iCntr];
         if(value>max)
             break;
         if(value >=min && value <=max){
             subArray[jCntr++]= value;
         }
    }
    return subArray;
}

由于数组是按升序排列的，如果我得到的值比参数中提供的最大值还要大，我将中断循环。

是否有其他更有效的方法从JavaScript数组中获取值？

- Hardik Mishra

---

http://www.w3schools.com/jsref/jsref_slice_array.asp - Roest

@Roset：我没有起始索引和结束索引，我只有数值。 - Hardik Mishra

不是使用数组，而是可以使用更适合的数据结构，比如区间树。 - Esailija

@Esailija，那么只需使用其他的最终条件而不是等式即可。 - Oleg V. Volkov

@Esailija 二分查找可以确定大于给定值的最小元素和小于给定值的最大元素。你否认吗？.. - Qnan

Answer 1

这里有一种半二进制过滤方法，看起来比较高效（至少在我的浏览器 - Chrome，Firefox，IE9）（参见测试结果）。

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;   
}

- KooiInc

---

这段代码可能会更高效，但我知道某些浏览器不支持 Array.filter。 - Qnan

请注意，中间值被输出了两次，例如 filterBinary([0,1,2], 0, 2) == [0, 2, 1, 1]。此外，这不是二分查找，所以您应该重新命名该方法 :-) - Bergi

Answer 2

你可以使用二分查找获取索引，然后使用切片：

Array.prototype.sliceRange = function(min, max) {
    if (min > max) return this.sliceRange(max, min);
    var l = 0,
        r = this.length;
    // find an element at index m that is in range
    rough: {
        while (l < r) {
            var m = Math.floor(l + (r - l) / 2);
            if (this[m] < min)
                l = m + 1;
            else if (this[m] > max)
                r = m;
            else
                break rough;
        }
        // l == r: none was found
        return [];
    }
    var lr = m, // right boundary for left search
        rl = m; // left boundary for right search
    // get first position of items in range (l == lr)
    while (l < lr) {
        m = Math.floor(l + (lr - l) / 2);
        if (this[m] < min)
            l = m + 1;
        else
            lr = m;
    }
    // get last position of items in range (r == rl)
    while (rl < r) {
        m = Math.floor(rl + (r - rl) / 2);
        if (this[m] > max)
            r = m;
        else
            rl = m + 1;
    }
    // return the items in range
    return this.slice(l, r);
}

(演示)

---

然而，@Qnan的方法只进行了一个半搜索（而不是我三个半搜索），更加直接，不应该遇到任何缺点。我只会使用导致精确索引的循环：

Array.prototype.sliceRange = function(min, max) {
    if (min > max) return this.sliceRange(max, min);
    var l = 0,
        c = this.length,
        r = c;
    // get first position of items in range (l == c)
    while (l < c) {
        var m = Math.floor(l + (c - l) / 2);
        if (this[m] < min)
            l = m + 1;
        else
            c = m;
    }
    // get last position of items in range (c == r)
    while (c < r) {
        var m = Math.floor(c + (r - c) / 2);
        if (this[m] > max)
            r = m;
        else
            c = m + 1;
    }
    // return the items in range
    return this.slice(l, r);
}

- Bergi

---

min和max不一定在数组中，因此它们可能会返回-1。二分查找也会返回-1，但速度更快。 - Esailija

@Esailija：通过二分搜索，我指的是一种返回在范围内的元素索引的二进制算法，而不是搜索最小/最大值本身。仍在努力编写代码 :-) - Bergi

嘿，很高兴看到你现在已经把它搞定了。之前也有一个无限循环。 - Esailija

是的，那是因为最后一个中间指针需要使用ceil而不是floor进行计算。 - Bergi

@Esailija 因为在底部你有 r+1。 - Max S.

Answer 3

尝试像这样优化循环（在达到最大值后从排序列表中退出）的问题在于每次迭代都要进行一次检查。有时直接遍历整个列表更快，特别是当您搜索的值位于列表末尾时（例如更近的日期）。但是，如果有所区别，您需要使用二进制搜索算法。Lodash具有使用二进制搜索检索应插入值的索引的函数。将其与slice结合使用，结果应该是最佳的。

使用[Lodash][1]

[1]:https://lodash.com/

// sliced :  get all values between+including min-max from sorted array of numbers
// @param array sorted timestamps
// @param min timestamp minimum
// @param max timestamp maximum
function sliced(array,min,max){
    return array.slice(_.sortedIndex(array, min),_.sortedIndex(array, max)+1);
}

- Shanimal

Answer 4

以下大致是在这种情况下二分查找的样子

var dates = [1333391400000,1335292200000,1335810600000,1336329000000,1336933800000,1337020200000,
1337193000000,1337538600000,1337625000000,1337797800000,1338316200000,1338921000000,
1339093800000,1339439400000,1340303400000,1341772200000,1342463400000,1343068200000];

function getDatesBetweenRange(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;
}

console.log(getDatesBetweenRange(1337193000000, 1337797800000));​

这是基于@Stano的代码，不过二分查找运行了两次以确定更紧密的边界。当然，它可以改进。

这里是 jsfiddle 的链接：http://jsfiddle.net/EJsmy/1/

- Qnan

---

我明白你的意思，即通过识别比给定值更大的值，并承认我没有足够地跳出思维定势，以便看到可以通过线性检查搜索给定的边界来进行清理。我想得更多的是像.slice(bs(min),bs(max))这样的方式，当然这是不可能的。我将把这个答案放在bergi的上面。 - Esailija

是的，界限需要进行调整，但很容易证明这种调整不会超过O(1)的时间，因此整体的O(log(n))得以保留：http://jsfiddle.net/3VR4k/4/; 附注：抱歉，我的上一个评论包含了错误的fiddle链接。 - Qnan

@Bergi 没有，起点是小于等于最小值的。当我调整边界时就会处理它。不过我必须承认你的解决方案更优雅。 - Qnan

@Qnan 是的，我正在更多地从概念层面上评估它。在 Chrome 中，.push 和循环通常比 [].slice.call 快得多，至少在我上次检查时是这样。 - Esailija

这是所有已发布代码以及OP代码的jsperf http://jsperf.com/filterarray/3 - Esailija

Answer 5

  function getDatesBetweenRange(min,max)
    {   
      var subArray = dates.slice(0,dates.length-1);

      for(var iCntr=0;iCntr<dates.length;iCntr++)
       {
       if(!(dates[iCntr] >=min && dates[iCntr] <=max))
          {
             subArray.splice(iCntr,1); 
          }
        }
       return subArray; 
   } 

- perilbrain

---

这将同时更改原始的“dates”数组。 - Oleg V. Volkov

这样做不行。它会移除 iCntr 位置的一个元素。 - Ashwin Prabhu

@OlegV.Volkov：现在可以了吗？ - perilbrain

@AshwinPrabhu：在尝试编辑器中尝试过了，它可以工作（w3school）。 - perilbrain

@匿名用户，不行。你正在进行浅复制，而根据问题的定义，原始数组中可能有许多元素。这会大大降低性能。 - Oleg V. Volkov