Dear Matteo and Nis, Thankyou very much for your help. I wasn't aware of the bisect library but it's really useful. thank you both once again Lee
On 13 Jun, 23:21, Nis Jørgensen <[EMAIL PROTECTED]> wrote: > 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
