搜索算法

Question

我有一个包含10k记录的JSON。每个记录都有一个时间戳，其格式为'2011-04-29'。现在我有了一个客户端数组(让我们称之为我们的日历)，其中包含了表单数组-

['2011-04-26', '2011-05-02', 'Week 1', '2010 - 11']
...

目标是为每个记录的时间戳分配一个星期号。我可以使用经典的线性搜索来完成这个任务，但是有了10k+ json记录和日历上将近300个星期的时间，这很快就变得乏味了。

你有什么推荐的？

我需要日历，因为这里的周不是一年中的实际一周，而是定义了其他地方。

如果我将字符串转换为Date.getTime()，是否有一种更有效的方法来做到这一点？

Answer 1

只有300周的时间，我的方法是引入一个中间查找对象，将每个可能的时间戳匹配到适当的周。只需使用一个简单的循环，它将生成：

{
    '2011-04-26': 1,
    '2011-04-27': 1,
    // ...
    '2011-05-02': 1,
    '2011-05-03': 2,
    '2011-05-04': 2,
    // ...
}

这些值只是calendar数组中的索引。

然后，您可以将10K的记录分配给一个日历周，只需在这个对象中进行简单的查找。

Answer 2

只要以某种方式对日历记录进行排序，就可以在其上应用二进制搜索算法。如果要将日期保存为时间戳而不是字符串，则可能会使比较更快(尽管对于当前格式，字符串比较也有效)。

用“周”索引你的日历可能会更优雅。有点像

{
  "Week 1": ['2011-04-26', '2011-05-02', '2010 - 11'],
  "Week 2": ['2011-05-03', '2011-05-09', '2010 - 12'],
  ...
}

请注意，从calendar数组创建这个查找对象的复杂性为O(n)，因此，如果只需要搜索一条记录，即使对原始数组进行线性搜索也会更快。

原始数组的示例算法：

var calendar = [
  ['2011-04-26', '2011-05-02', 'Week 1', '2010 - 11'],
  ['2011-05-03', '2011-05-09', 'Week 2', '2010 - 12'],
  ...
];
function getRecord(date) {
    var l = 0,
        r = calendar.length-1;
    while (l <= r) {
        var m = ~~(l + (r-l)/2);
        var comp = comparefn(this[m]);
        if (calendar[m][1] < date) // last day of week before date
            l = m+1;
        else if (calendar[m][0] > date) // first day of week after date
            r = m-1;
        else // week found
            return calendar[m];
    }
    // I'm not quite sure what happens when a date lies between two weeks in the calendar
    return null;
}