On Dec 14, 12:05 pm, Dave Hansen <[EMAIL PROTECTED]> wrote:
> On Dec 13, 5:45 pm, Breal <[EMAIL PROTECTED]> wrote:
>
> > I have a list that looks like the following
> > [(100000, 100010), (100005, 100007), (100009, 100015)]
>
> > I would like to be able to determine which of these overlap each
> > other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
> > 2 overlaps with 1. Tuple 3 overlaps with tuple 1.
>
> > In my scenario I would have hundreds, if not thousands of these
> > ranges. Any nice pythonic way to do this?
>
> What are you going to do with the result? Do you need to know if
> there are any overlaps? The number of overlaps? Given any particular
> range, what ranges overlap?
>
> There's really no way, other than to compare each range. Note that
> the relationship is symmetric, so you can save half you work. A
> simple-minded approach might be
>
> ---
>
> def overlaps(t1, t2):
> return (t2[1] >= t1[0]) and (t2[0] <= t1[1])
>
> in_data = [(100000, 100010), (100005, 100007), (100009, 100015)]
>
> while (len(in_data) > 1):
> target = in_data.pop(0)
A tad excessive:
pop(0) is O(N)
pop() is O(1)
Pythonic and likely to be faster, Take 1:
while in_data:
target = in_data.pop()
Pythonic and likely to be faster, Take 2:
while 1:
try:
target = in_data.pop()
except IndexError:
break
> for test in in_data:
> if overlaps(target,test):
> print "%s overlaps with %s" % (repr(target),repr(test))
Cheers,
John
--
http://mail.python.org/mailman/listinfo/python-list
