From: LAMBEAU Bernard <blambeau@...>
Date: 2009-04-13T02:45:05+09:00
Subject: Re: more efficient date range comparison

First of all, you could return true as soon as you find a conflict
instead of counting them. However, it does not change anything from a
theoretical point of view: your method executes in O(n*m) time which
means that if recurrences has n entries and other.recurrences has m
entries, then the time spent in the method is a function of n*m in the
worst case: when no conflict arrises your method checks all pairs.

If I understand your need correctly (I'm not sure to understand what
an occurence is exactly), it seems that you could write an algorithm
that executes in O(m+n), which is really better. By sorting your
ranges, you could avoid many useless comparisons. It reminds me a
couple of algorithms that I've written a few month ago and which
computes the union/intersection of composite intervals. You can have a
look at code.chefbe.net: there's a project called CRUC with a well
documented class named Interval (rdoc is online) which contains these
algorithms.

I hope this helps (let me know)
blambeau

On Sun, Apr 12, 2009 at 2:11 PM, Dave Woodworth <user296@gmail.com> wrote:
> Hello all
>
> I'm writing a calendar application that needs to check for conflicts
> between recurring entries. Each Entry object has a recurrences() method
> which returns an array of ranges - each range contains the start and end
> times of each future occurence.
>
> I need to check for conflicts between new and existing entries. I'm
> doing this by checking that none of the future occurences of the new
> entry clash with future occurences of existing entries:
>
> def conflicts?(other)
>  conflicts = 0
>  recurrences.each do |my_rec|
>    other.recurrences.each do |other_rec|
>      start, finish = other_rec.first, other_rec.last
>      conflicts += 1 if my_rec.include?(start) ||
> my_rec.include?(finish)
>    end
>  end
>  conflicts > 0
> end
>
> recurrences() defaults to returning all occurences between start time
> and start time + 1 year
>
> the problem is this method is not the most efficient in the world.
> comparing just two entries, each with a daily recurrence over 1 year,
> leads to 365 * 365 comparions (on my machine that takes 4+ seconds).
> There may be any number of existing entries to compare a new entry to so
> the method I have now is useless.
>
> I don't have a computer science or maths background but I've been
> reading various textbooks on algorithms and I havn't been able to find a
> way to optimize the method. Does anyone else have any ideas?
>
> thanks
> Dave
> --
> Posted via http://www.ruby-forum.com/.
>
>