これが私の基本的な問題ですcurrentTime
。たとえば、750 秒です。また、1000 ~ 2000 個のオブジェクトを含む配列もあり、それぞれに、、、startTime
およびendTime
属性があり_id
ます。が与えられた場合、その範囲内にあるとcurrentTime
を持つオブジェクトを見つける必要があります。たとえば、。startTime
endTime
startTime : 740
endTime : 755
Javascriptでこれを行う最も効率的な方法は何ですか?
手始めに、私は単にこのようなことをしてきました:
var arrayLength = array.length;
var x = 0;
while (x < arrayLength) {
if (currentTime >= array[x].startTime && currentTime <= array[x].endTime) {
// then I've found my object
}
x++;
};
しかし、ループはここでは最良の選択肢ではないと思います。助言がありますか?
編集: わかりやすくするために、はandcurrentTime
内に収まる必要がありますstartTime
endTime
私の解決策:私のデータの構造には、物事を少し単純化できる特定の利点があります。配列は既に startTime でソートされているため、示唆されているように、基本的なバイナリ検索を実行しました。この速度を完全にテストしたわけではありませんが、特に大規模な配列では、かなり高速であると思われます。
var binarySearch = function(array, currentTime) {
var low = 0;
var high = array.length - 1;
var i;
while (low <= high) {
i = Math.floor((low + high) / 2);
if (array[i].startTime <= currentTime) {
if (array[i].endTime >= currentTime ){
// this is the one
return array[i]._id;
} else {
low = i + 1;
}
}
else {
high = i - 1;
}
}
return null;
}