CODEWITHSUNDEEP
javascriptsearch
Jibi Abraham
Jibi Abraham

Reputation: 4696

Search algorithm

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()?

Upvotes: 0

Views: 163

Answers (2)

Bergi
Bergi

Reputation: 664503

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

Upvotes: 1

Scott Sauyet
Scott Sauyet

Reputation: 50787

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.

Upvotes: 2

Related Questions