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 は、特に配列のサブセットを取得するための非常にシンプルな方法が必要な場合に、素晴らしい反応を示しました。ただし、サブ配列全体ではなく、サブ配列のインデックスが必要でした。私はいくつかのテストを行いましたが、上記の例では、1,000 万のエントリを持つ配列であっても、サブ配列の境界を見つけるのに一貫して約 7 ミリ秒かかります!

正しい方向に向けてくれた@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 をサポートする必要がある場合は、shim を実行できます:

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 に答える