1

我有一系列顺序时间戳。我需要获取介于开始时间和结束时间之间的数组子集。一个简化的示例如下所示：

timestamps = [ 5,7,12,13,15,23 ];
startTime  = 6;
endTime    = 18;

给定上面的例子，找到介于startTime和之间的第一个和最后一个时间戳的索引的最有效方法是endTime什么？

正确的脚本会发现并返回索引 1 和 4 ( timestamps[1], timestamps[4])

我可以遍历数组并进行比较，但有没有更有效的方法？

编辑 :: 我的解决方案 - 二进制搜索：

（咖啡稿）

 # Search ordered array for timestamps falling between 'start' & 'end'
 getRangeBorderIndexes = (stack, start, end) ->
  ar    = []
  ar[0] = getBorder( stack, start, "left" )
  ar[1] = getBorder( stack, end, "right"  )
  return ar

# Use bisection (binary search) to find leftmost or rightmost border indexes
getBorder = (stack, value, side ) ->
  mod1       = if side == "left"  then 0 else -1 
  mod2       = if side == "left"  then 1 else  0

  startIndex = 0
  stopIndex  = stack.length - 1
  middle     = Math.floor( (stopIndex+startIndex)/2 )

  while stack[middle] != value && startIndex < stopIndex
    if value < stack[middle]
      if value > stack[middle - 1] then return middle + mod1
      stopIndex = middle - 1

    else if value > stack[middle]
      if value < stack[middle + 1] then return middle + mod2
      startIndex = middle + 1

    middle = Math.floor( (stopIndex+startIndex)/2 )

  return if stack[middle] != value then -1 else middle

timestamps = [ 5,7,12,13,15,23 ]
startTime  = 6
endTime    = 18

getRangeBorderIndexes( timestamps, startTime, endTime) # returns [1,5]

@kennebec 和 @Shanimal 给出了很好的回应，特别是如果您想要一种超级简单的方法来获取数组的子集。但是我需要子数组的索引而不是整个子数组。我做了一些测试，上面的示例始终需要大约 7 毫秒才能找到子数组的边界，即使在具有 1000 万个条目的数组上也是如此！

感谢@voithos 为我指明了正确的方向。我还修改了这段代码来创建上面的解决方案。

4

2 回答 2

2

使用 lodash / underscore 库：

_.select(timestamps,function(i){
    return i>=startTime && i<=endTime;
})
于 2013-03-04T17:02:51.393 回答
1

循环是有效的，但 Array.filter 更容易 -

var timestamps = [ 5,7,12,13,15,23 ],

startTime  = 6,
endTime    = 18;


var selected=timestamps.filter(function(itm){
return itm>=startTime   && itm<=endTime;
});

/* 返回值：（数组）7,12,13,15 */

// 大多数浏览器都内置了过滤器，但如果你需要在#9 之前支持 IE，你可以填充它：

if(!Array.prototype.filter){
    Array.prototype.filter= function(fun, scope){
        var T= this, A= [], i= 0, itm, L= T.length;
        if(typeof fun== 'function'){
            while(i<L){
                if(i in T){
                    itm= T[i];
                    if(fun.call(scope, itm, i, T)) A[A.length]= itm;
                }
                ++i;
            }
        }
        return A;
    }
}
于 2013-03-04T17:11:08.160 回答