lesande at gmail.com
Thu Jun 14 11:27:20 CEST 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
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
> 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
> # 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] == ivl:
> if intervals[idx] >= ivl:
> return idx
> return None
> # Otherwise, we need to check to the left of the insertion point
> if idx > 0 and intervals[idx-1] >= ivl:
> return idx-1
> return None
> >>> intervals =[(10, 21), (34, 51), (77, 101)]
> >>> print test_interval((34,35),intervals)
> >>> print test_interval((34,53),intervals)
> >>> print test_interval((77,53),intervals)
> >>> print test_interval((77,83),intervals)
> >>> print test_interval((77,102),intervals)
> >>> print test_interval((77,101),intervals)
> u"Nis J\xf8rgensen"
More information about the Python-list