Page 1 of 1

Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 10:47 am
by whisperstream
I think this probably is better situated in PHP - Code, to which I have moved it, leaving a 'shadow' topic in PHP - Theory and Design.

Not sure if this is the right place and apologies to any moderator who feels it should be moved to a different forum.

Anyway, I building a Calendar object to hold an array of Event objects (each object simply has a title, start_date, end_date).

I want to be able to call the following:

Code: Select all

// events that start on/after $start and end on/before $end
$events = $calendar->getEventsBetweenDates($start, $end);
 
// returns events that start or end anywhere within the specified range
// (hmm suggestions for a better method name are welcome)
$events = $calendar->getEventsOverDates($start, $end);
Anyway this is trivial to accomplish using a foreach loop and looping through each event and comparing the $start and $end date to the event's $start or $end date.

E.g. To implement the method getEventsBetweenDates($start, $end) you can easily do the following

Code: Select all

 
foreach($eventArray as $evt)
{
    if( ($start <= $evt->start && $evt->end <= $end)
    {
         $result[] = $evt;
    }
}
E.g. Similarly to implement the method getEventsOverDates($start, $end) you can easily do the following

Code: Select all

 
foreach($eventArray as $evt)
{
    if( ($start <= $evt->start && $evt->end <= $end)
        || ($evt->start <= $start && $evt->end => $end)
        || ($start => $evt->start && $evt->start <= $end)
        || ($evt->end >= $start && $evt->end <= $end))
    {
         $result[] = $evt;
    }
}
What I don't like here is that it's pretty inefficient because I have to start at the start and loop through all entries so I'm wondering if anyone knows of a good way to organise the array and use a better searching algorithm than just looping through the entries. I did look a bit at using a binary search algorithm but you'd need two (one for the start dates and one for the end dates) and then you have to merge your set of results from the start index with the ones that matched against the end index, and this also seems like overkill.

I should add that I'm using the Zend Framework, but I didn't see anything there that helps here. I checked out Zend_Search_Lucene to see if they had an in-memory implementation, but they didn't and the documentation said it was quite intensive which probably translates into overkill for this class.

Re: Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 11:19 am
by arjan.top
whisperstream wrote: I did look a bit at using a binary search algorithm but you'd need two (one for the start dates and one for the end dates) and then you have to merge your set of results from the start index with the ones that matched against the end index, and this also seems like overkill.
Merge what?

just find start and end date, than use array_slice

Re: Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 11:27 am
by whisperstream
Hmm maybe I'm missing something, how does array_slice work in this context?

I need to find the smallest start date that matches $start and the largest end date that matches $end. If I was just concerned about finding any dates that started on/after $start, or just concerned about events that ended on/before $end, then I could use array_slice. But by searching for start and end and if using array slice, as far as I can see I would need two arrays, one with events indexed by start time, one indexed by end time. Then when searching for both start and end dates I would have to slice each array at some particular point and intersect them to get the specified range I'm looking for.

Re: Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 1:54 pm
by arjan.top
ignore what I wrote in previus post, I don't know why but I thought every object has one date, not the end and start ...

you could sort array by start date and search for it, then search for end date in all objects >$start

Re: Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 2:13 pm
by califdon
I'm not very adept with arrays, but I'm wondering if filling an array with this data is the best approach to begin with. If the number of entries is small, the differences in search logic will be negligible, and if the number of entries is large, why not let them remain in the database and let SQL handle it easily? I hope I'm not missing the point, but maybe I am.

Re: Efficient Calendar Searching?

Posted: Sat Oct 18, 2008 6:36 pm
by whisperstream
califdon wrote:I'm wondering if filling an array with this data is the best approach to begin with. If the number of entries is small, the differences in search logic will be negligible, and if the number of entries is large, why not let them remain in the database and let SQL handle it easily? I hope I'm not missing the point, but maybe I am.
No you're not missing the point at all, it's a good point and I plan to extend this class (maybe with an adapter or inherit from this base class and override to provide access to a database). I just wondered if anyone could think of a better way of storing this data to make searching it efficient.