0

我有一个 JSON，里面有 10k 条记录。每条记录都有一个格式为'2011-04-29'的时间戳。现在我有一个客户端数组（我们称它为我们的日历），其数组形式为 - 

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

目标是为每条记录的时间戳分配一个星期数。我可以使用经典的线性搜索来完成此操作，但是由于 10k+ json 记录和日历中接近 300周，这很快就会变得乏味。

你会推荐什么？

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

如果我将字符串转换为 ，会有更有效的方法Date.getTime()吗？

4

2 回答 2

2

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

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

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

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

于 2012-07-18T12:17:56.537 回答
1

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

按“周”索引您的日历可能更优雅。就像是

{
  "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;
}
于 2012-07-18T12:25:55.573 回答