Efficient Calendar Searching?

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
whisperstream
Forum Newbie
Posts: 3
Joined: Sat Oct 18, 2008 10:19 am

Efficient Calendar Searching?

Post 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.
User avatar
arjan.top
Forum Contributor
Posts: 305
Joined: Sun Oct 14, 2007 4:36 am
Location: Hoče, Slovenia

Re: Efficient Calendar Searching?

Post 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
whisperstream
Forum Newbie
Posts: 3
Joined: Sat Oct 18, 2008 10:19 am

Re: Efficient Calendar Searching?

Post 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.
User avatar
arjan.top
Forum Contributor
Posts: 305
Joined: Sun Oct 14, 2007 4:36 am
Location: Hoče, Slovenia

Re: Efficient Calendar Searching?

Post 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
User avatar
califdon
Jack of Zircons
Posts: 4484
Joined: Thu Nov 09, 2006 8:30 pm
Location: California, USA

Re: Efficient Calendar Searching?

Post 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.
whisperstream
Forum Newbie
Posts: 3
Joined: Sat Oct 18, 2008 10:19 am

Re: Efficient Calendar Searching?

Post 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.
Post Reply