mapping subintervals
Lee Sander
lesande at gmail.com
Thu Jun 14 05:27:20 EDT 2007
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 <n... at superlativ.dk> 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"
More information about the Python-list
mailing list