javascript - 插入有序数组的计算效率最高的方法？

Question

我有一个包含时间序列数据的数组，如下所示:

var timeseries = [
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2],
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3],
    [Tue Dec 31 2013 02:00:00 GMT+0000 (GMT Standard Time), 4, 2]
]

嵌套数组中的第一项是 javascript 日期。

我有第二个数组，其中包含一个唯一的 javascript 日期列表，但timeseries 数组中可能已经存在也可能不存在:

var newTimes = [
    Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 01:40:00 GMT+0000 (GMT Standard Time)
]

对于 newTimes 数组中的每一项，我需要检查该日期是否存在于与 timeseries 数组一起存储的数组中。如果没有，我想在正确的位置(按时间顺序)将一个新数组插入到时间序列数组中，并且 - 至关重要的是 - 从直接在前的数组中复制其他数组值。例如，将上述两个数组组合起来会产生:

var newTimeseries = [
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2],
    [Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 3, 2],
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3],
    [Tue Dec 31 2013 01:40:00 GMT+0000 (GMT Standard Time), 1.2, 3],
    [Tue Dec 31 2013 02:00:00 GMT+0000 (GMT Standard Time), 4, 2]
]

我应该注意到两个数组都已经排序了。此外，newTimes 中的项目将存在于 timeseries 范围内。最后，原始 timeseries 数组每小时都有一个条目，在整点。

我尝试了几种不同的方法，但我对计算效率最高的方法感兴趣。如果有帮助，我很乐意使用任何适当的、被广泛采用的第三方库，例如 underscore.js。

Answer 1

在考虑了二分搜索(由 techfoobar 在评论中建议)和冒泡排序 (friendzis) 之后，到目前为止我想出的最佳解决方案是遵循这个逻辑。

与使用二分搜索相反，请考虑以下内容。

因为我们知道两个数组都已经排序了； newTimes 中的日期在 timeseries 日期范围内；并且初始的 timeseries 条目是在整点，每小时，我们可以找到 timeseries[0][0] 日期和 newTimes[0] 之间的小时差。这是启动冒泡排序方法所需的初始偏移量(更像是上面评论中讨论的标准循环和切片)。这使用了 Moment.js 库。

代码如下，欢迎提出修改建议:

var firstEvent = moment(newTimes[0]);
var firstTime = moment(timeseries[0][0]) ;
var offset = firstEvent.diff(firstTime, 'hours') - 1; 


for (var i = offset; i < timeseries.length;i++) { 
    while (newTimes.length > 0 && typeof moment(timeseries[i+1]) !== "undefined" && moment(newTimes[0])  > moment(timeseries[i][0]) && moment(newTimes[0])  < moment(timeseries[i+1][0])) {
        var newElement = timeseries[i].slice(0);
        newElement[0] = moment(newTimes[0]).toDate();
        timeseries.splice(i+1, 0, newElement);
        newTimes.splice(0,1);
        i++;
    } 
}

重要的是，当 newTimes 数组中有两个或多个条目都属于一个 timeseries 条目时，这可以应对边缘情况，例如:

var timeseries = [
    [Tue Dec 31 2013 00:00:00 GMT+0000 (GMT Standard Time), 3, 2],
    [Tue Dec 31 2013 01:00:00 GMT+0000 (GMT Standard Time), 1.2, 3]
]

var newTimes = [
    Tue Dec 31 2013 00:13:00 GMT+0000 (GMT Standard Time), 
    Tue Dec 31 2013 00:16:00 GMT+0000 (GMT Standard Time)
]