Search algorithm

Question

I have a JSON with a say 10k records in it. Each record has a timestamp of the form '2011-04-29'. Now I have a client side array (let's call it our calendar) with arrays of the form -

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

The goal is to assign a week number to each record's timestamp. I could use a classical linear search to accomplish this, but with 10k+ json records and close to 300 weeks in the calendar, this soon becomes tedious.

What would you recommend?

PS - I need the calendar because the weeks here are not the actual week of the year, but defined else where.

Would there be a more efficient way of doing this if i converted the strings to Date.getTime()?

What exactly are you searching for? Kind of "all arrys in calendar where week==1"? — Bergi, Jul 18 '12 at 12:15
@Bergi - find one array where the timestamp fits in between array[0] - start date - and array[1] - end date — Jibi Abraham, Jul 18 '12 at 12:17
And how many searches/results do you expect? If you only search for one record, building an index (or similiar) for *all* elements is not efficient. — Bergi, Jul 18 '12 at 12:17
What exactly are your weeks? ISO-weeks? Is there an algorithm or do you need this lookup table? — Bergi, Jul 18 '12 at 12:21
They are business weeks, hence the absolute need for the look up table — Jibi Abraham, Jul 18 '12 at 12:21

score 2 · Accepted Answer · answered Jul 18 '12 at 12:17

With only 300 weeks, my approach would be to introduce an intermediate lookup object, matching each possible timestamp to the appropriate week. Just use a simple loop that will generate:

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

Those values would simply be indices in your calendar array.

Then you can assign your 10K of records to a calendar week with a simple lookup in this object.

I like this approach, tx Scott – Jibi Abraham Jul 18 '12 at 12:20 — Jibi Abraham, Jul 18 '12 at 12:20

Bergi · Answer 2 · 2012-07-18T12:41:46.283

As far as your calendar records are ordered in some way, you can apply a binary search algorithm on it. If you would save the dates as timestamps instead of strings, it might make comparisons faster (although for your current format, string comparison also works).

It might be more elegant to index your calendar by "weeks". Something like

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

Note that the creation of this lookup object from your calendar array has a complexity of O(n), so if you only need to search for one record even a linear search on the original array would be faster.

Sample algorithm for your original array:

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;
}

integer-truncation, see [What is the “double tilde” (~~) operator in JavaScript?](http://stackoverflow.com/questions/5971645/what-is-the-double-tilde-operator-in-javascript) — Bergi, Jul 18 '12 at 12:45

Search algorithm

2 Answers2