如何减少检查值数组是否在另一个范围数组之间的循环次数

Question

我正在尝试检查一个时间是否在一系列间隔内，我知道如何进行比较...等等但是我担心效率，因为我需要检查很多时间条目（6,000,000 ) 并且我使用的服务提供的处理时间有限。

现在我有一个包含 48 个时间范围的数组，一天 24 小时分成 30 分钟的时间间隔。我用 6000k 条目中的每一个循环遍历此数组，以查看条目介于两者之间。所以我需要执行 288,000,000 次循环，每个循环有 2 次条件检查。

所以这几乎是 O(n*48)。

可以通过哪些方式改进？这是在 JavaScript.

按要求编辑代码：

示例间隔：

开始：new Date(0,0,0,1,30,0)
结束：new Date(0,0,0,2,0,1)

示例时间：（我将时间字符串转换为日期，如第二个项目符号所示）

'2015-12-03 15:25:00'
new Date(0,0,0,15,25,0)

示例循环：

for(var i = 0; i < myArray.length; i++)
{
    for(var ii = 0; ii < myIntervals.length; ii++)
    {
        if(myArray[i] >= myIntervals[ii].start && myArray[i] <= myIntervals[ii].end)
        {
            myIntervalCounts[ii] ++;
        }
    }
}

Answer 1

根据对问题的理解，您有 6kk 个条目，形式为“11:37 AM”、“10:00 PM”和 48 个时间段，每个时间段 30 分钟，并且您将它们标记为 (例如，11:37 AM 在第 23 个标签中，索引为 0）。

我相信时间条目只需要一个循环：

function label_timestamp(hour,minute,period)
   return hour*2 + (period==="PM")*24 + (minute>30)*1 )

for (e in entries) 
   console.log(label_timestamp(e.hour, e.minute, e.period)

这样 11:37 AM 变成 11*2+0*24+1*1=23

这个是O(n)，但是问题又不是很清楚

Answer 2

嗯，如果你的 time-ranges 排队，你可以这样做：

var start = myIntervals[0].start, 
    end = myIntervals[myIntervals.length-1].end,
    segment = (end-start) / myIntervals.length;

for(var i=0, j=myArray.length; i<j; ++i){
    var v = myArray[i];

    if(v < start || v >= end) continue;
    var ii = ((v - start)/segment) >>> 0;
    myIntervalCounts[ii]++; 
}

假设区间是排序的，否则你需要添加一些映射

如何减少检查值数组是否在另一个范围数组之间的循环次数

How to reduce the number of loops for checking if an array of values is in between another array of ranges

javascript

performance

big-o

google-apps-script