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.