complaints about no replies last week
Steven D'Aprano
steve at REMOVE-THIS-cybersource.com.au
Mon Mar 30 11:57:49 EDT 2009
On Mon, 30 Mar 2009 07:50:49 -0700, pruebauno wrote:
> I myself asked about how to write a library to efficiently do union and
> intersection of sets containing time intervals some time ago on this
> list and got little to no answers. It is a tricky problem.
With all the confidence of somebody who doesn't need to solve it, I can
say, no, it's an easy problem, provided you use the correct data
structure. What you want is an interval tree:
http://en.wikipedia.org/wiki/Interval_tree
> Since I was
> getting paid I got an O(n*n) solution working.
Just off the top of my head, I *think* you should be able to get that
down to O(m * log n) where m is the size of one set and n the size of the
other. Don't quote me on that though.
> People on this list on the other hand do not get paid
We don't??? Damn! I was expecting a HUGE cheque at the end of the month!
BTW Aaron, I haven't replied to your post about the garbage collector
because that's one part of Python programing where I cherish my ignorance.
--
Steven
More information about the Python-list
mailing list