464,528 Members | 938 Online Need help? Post your question and get tips & solutions from a community of 464,528 IT Pros & Developers. It's quick & easy.

# Determing whether two ranges overlap

 P: n/a Hey guys I was wondering if you could give me a hand with something. If I have two tuples that define a range, eg: (10, 20), (15, 30), I need to determine whether the ranges overlap each other. The algo needs to catch: (10, 20) (15, 25) (15, 25) (10, 20) (10, 25) (15, 20) and (15, 20) (10, 25) I can think of lots of ways to do this but it's in a tight loop so I need it to be as efficient as possible. Any help welcome :-) Cheers -Rob Feb 16 '06 #1
6 Replies

 P: n/a Robin Haswell wrote: Hey guys I was wondering if you could give me a hand with something. If I have two tuples that define a range, eg: (10, 20), (15, 30), I need to determine whether the ranges overlap each other. def overlap(a,b): return a <= b <= a or b <= a <= b -- Paul Feb 16 '06 #2

 P: n/a On Thu, 16 Feb 2006 15:22:15 +0000, Robin Haswell wrote: Hey guys I was wondering if you could give me a hand with something. If I have two tuples that define a range, eg: (10, 20), (15, 30), I need to determine whether the ranges overlap each other. The algo needs to catch: (10, 20) (15, 25) (15, 25) (10, 20) (10, 25) (15, 20) and (15, 20) (10, 25) What do you mean "catch"? Do you expect the algorithm to recognise these combinations as special and return something different? I'm going to assume that there are no magic values that need to be caught, because I don't know what that means, and just proceed as if the task is to compare two tuples of the form (x1, x2) where x1 <= x2. # warning: untested! def isoverlap((x1,x2), (y1,y2)): """Given two numeric ranges, returns a flag True or False indicating whether they overlap. Assumes that the ranges are ordered (smallest,largest). If that assumption is wrong, incorrect results may occur.""" # Fully overlapping cases: # x1 <= y1 <= y2 <= x2 # y1 <= x1 <= x2 <= y2 # Partially overlapping cases: # x1 <= y1 <= x2 <= y2 # y1 <= x1 <= y2 <= x2 # Non-overlapping cases: # x1 <= x2 < y1 <= y2 # y1 <= y2 < x1 <= x2 return not (x2 < y1 or y2 < x1) I can think of lots of ways to do this but it's in a tight loop so I need it to be as efficient as possible. "Efficient as possible" in what way? Least memory used? Smallest number of bytes of source code? Fastest performance? Assuming you need fastest performance, the general method to do that is to write it in hand-tuned assembly language, taking care to use all the tricks to optimize it for the particular CPU you are running on. If you can find a way to push the processing into any high-end graphics processors you might have, that typically will speed it up even more. It is still, sometimes, possible for the best assembly programmers to just barely outperform optimizing C compilers, or so I'm told. If you are willing to set your sights just a little lower, and rather than aiming for the absolute fastest code possible, settle for code which is fast enough, the usual technique is to stick to Python. Write different functions implementing the various methods you can think of, and then time them with the timeit module. Pick the fastest. Is it fast enough that performance is satisfactory? If so, then you are done. Here is a technique that may speed your code up a little: it is quicker to find local variables than global. So, instead of this: def main(): ... code here ... while condition: flag = isoverlap(t1, t2) ... code ... you can gain a little speed by making a local reference to the function: def main(): ... code here ... iso = isoverlap # make a local reference for speed while condition: flag = iso(t1, t2) ... code ... If your code is still too slow, you might speed it up with Psycho, or you may need to write a C extension. Either way, you won't know if the code is fast enough until you actually run it. -- Steven. Feb 16 '06 #3

 P: n/a Robin Haswell wrote: I was wondering if you could give me a hand with something. If I have two tuples that define a range, eg: (10, 20), (15, 30), I need to determine whether the ranges overlap each other. The algo needs to catch: (10, 20) (15, 25) (15, 25) (10, 20) (10, 25) (15, 20) and (15, 20) (10, 25) I can think of lots of ways to do this but it's in a tight loop so I need it to be as efficient as possible. Any help welcome :-) how about: def overlap(a, b): return a > b and a < b Feb 16 '06 #4

 P: n/a Thanks guys, you've all been very helpful :-) -Rob Feb 17 '06 #5

 P: n/a Robin Haswell wrote: I can think of lots of ways to do this but it's in a tight loop so I need it to be as efficient as possible. Any help welcome :-) There are 24 possibilities of having 4 numbers in a row, and the following 6 of them describe nonempty intervals (the remaining 18 are obtained by reversing the endpoints of one or both intervals, thereby making them empty): # separate a0 a1 b0 b1 b0 b1 a0 a1 # inside a0 b0 b1 a1 b0 a0 a1 b1 # cross a0 b0 a1 b1 b0 a0 b1 a1 The simplest is to exclude the first pair, i.e. not (a1=b0 and b1>=a0, given by Fredrik without proof ;-) You will have to decide whether you want ">" or ">=" (beware of the former when using floats). If you cannot assume that the pairs are in order, this will break. Ralf Feb 17 '06 #6

 P: n/a Fredrik Lundh wrote: def overlap(a, b): return a > b and a < b Assuming that x can't be smaller than x, this is the right way to compare two ranges. Well, I guess you need to figure out the borderline cases. Is it a > b or a >= b which is relevant? Anyway, if we have N ranges and N is big, we'll get lots of comparisions: N*(N-1)/2. For large values of N, it might be better to somehow cache/aggregate the intervals if this makes it possible to make this into an N*M comparision where M is smaller than (N-1)/2.... E.g, with discrete values for the intervals such as with (10, 15), one might consider something like (untested): hits = sets.Set() for interval in intervals: for i in range(interval, interval+1): if i in hits: raise ValueError('%s overlaps previous interval.' % interval) hits.add(i) E.g. if we have 1000 intervals where the average size of an interval is 10, you get 10000 "i in hits" and "hits.add(i)" instead of 499500 'a > b and a < b'. As always, it's good to measure...assuming you have fairly realistic data to test with. Feb 22 '06 #7

### This discussion thread is closed

Replies have been disabled for this discussion. 