Matteo skrev:
> OK - I'm going to assume your intervals are inclusive (i.e. 34-51
> contains both 34 and 51).
>
> If your intervals are all really all non-overlapping, one thing you
> can try is to put all the endpoints in a single list, and sort it.
> Then, you can use the bisect module to search for intervals, which
> will give you a logarithmic time algorithm.
>
> Here, I'm going to assume you just need the index of the containing
> interval. If you really need a name (i.e. 'a1' or 'a2'), you can use a
> list of names, and index into that.
>
> I hope those assumptions are valid! if so, the following should work:
I have taken the liberty of simplifying your code, using the fact that
tuples are sorted lexicographically. Note that this requires all
intervals to be tuples and not lists (since list(a) < tuple(b) is always
True).
from bisect import bisect
def test_interval(ivl,intervals):
# Find where ivl would lie in the list
# i.e. the index of the first interval sorting as larger than ivl
idx=bisect(intervals,ivl)
# Left endpoints equal is a special case - a matching interval will be
# to the right of the insertion point
if idx < len(intervals) and intervals[idx][0] == ivl[0]:
if intervals[idx][1] >= ivl[1]:
return idx
else:
return None
# Otherwise, we need to check to the left of the insertion point
if idx > 0 and intervals[idx-1][1] >= ivl[1]:
return idx-1
else:
return None
>>> intervals =[(10, 21), (34, 51), (77, 101)]
>>> print test_interval((34,35),intervals)
1
>>> print test_interval((34,53),intervals)
None
>>> print test_interval((77,53),intervals)
2
>>> print test_interval((77,83),intervals)
2
>>> print test_interval((77,102),intervals)
None
>>> print test_interval((77,101),intervals)
2
u"Nis J\xf8rgensen"
--
http://mail.python.org/mailman/listinfo/python-list
