En Tue, 13 Jan 2009 02:55:36 -0200, Per Freem <perfr...@yahoo.com>
escribió:
On Jan 12, 10:58 pm, Steven D'Aprano
<ste...@remove.this.cybersource.com.au> wrote:
On Mon, 12 Jan 2009 14:49:43 -0800, Per Freem wrote:
> thanks for your replies -- a few clarifications and questions. the
> is_within operation is containment, i.e. (a,b) is within (c,d) iff a
>>= c and b <= d. Note that I am not looking for intervals that
> overlap... this is why interval trees seem to me to not be relevant,
i found an implementation (which is exactly how i'd write it based on
the description) here:
http://hackmap.blogspot.com/2008/11/python-interval-tree.html
when i use this however, it comes out either significantly slower or
equal to a naive search. my naive search just iterates through a
smallish list of intervals and for each one says whether they overlap
with each of a large set of intervals.
I think there is an algorithm by Baeza-Yates that handles efficiently what
you want; but I can't find it. Perhaps Google works better for you. It
might be only available in Spanish, though.
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
