complaints about no replies last week

Steven D'Aprano steve at REMOVE-THIS-cybersource.com.au
Mon Mar 30 17:57:49 CEST 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