473,386 Members | 1,864 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,386 software developers and data experts.

Determing whether two ranges overlap

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 18907

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[0] <= b[0] <= a[1] or b[0] <= a[0] <= b[1]

-- Paul

Feb 16 '06 #2
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
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[1] > b[0] and a[0] < b[1]

</F>

Feb 16 '06 #4
Thanks guys, you've all been very helpful :-)

-Rob
Feb 17 '06 #5
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 or b1<a0)

which simplifies to
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
Fredrik Lundh wrote:
def overlap(a, b):
return a[1] > b[0] and a[0] < b[1]


Assuming that x[1] can't be smaller than x[0], this
is the right way to compare two ranges. Well, I guess
you need to figure out the borderline cases. Is it
a[1] > b[0] or a[1] >= b[0] 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[0], interval[1]+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[1] > b[0] and a[0] < b[1]'.

As always, it's good to measure...assuming you have fairly
realistic data to test with.
Feb 22 '06 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Ben O'Steen | last post by:
Scenario: ========= Using PyGame in particular, I am trying to write an application that will run a scripted timeline of events, eg at 5.5 seconds, play xxx.mp3 and put the image of a ball on...
1
by: Jim Di Griz | last post by:
Hi I have a problem to create an XSD that prevents overlapping ranges. Sample XML: <root> <element LowerLimit="1" UpperLimit="50000"> ..... </element>
2
by: Manish Soni | last post by:
I am loading an assembly using reflection. Then I get all the methods in all types. I want to check whether a method is "unsafe". The MethodInfo class does not seem to provide this information. ...
3
by: Robert W. | last post by:
Long ago I developed a simple algorithm for calculating how much space is required to display a multi-line label in a limited width. It seemed to be working okay but then my testing revealed a...
67
by: PC Datasheet | last post by:
Transaction data is given with date ranges: Beginning End 4/1/06 4/4/06 4/7/06 4/11/06 4/14/06 4/17/06 4/18/06 4/21/06 426/06 ...
14
by: nishit.gupta | last post by:
Is their any single fuction available in C++ that can determine that a string contains a numeric value. The value cabn be in hex, int, float. i.e. "1256" , "123.566" , "0xffff" , It can also...
2
by: anoweb | last post by:
I have two ranges of numbers and I need to determine if they overlap or adjacent and if so return a new range containing the values. The values are low and high for each pair, such that the first...
3
by: Snedker | last post by:
Hi there, I really need some input of how to approach my little assignment. A customer wants to exclude all US IP-ranges from accessing part of his website. From...
7
by: guido | last post by:
Hi, I'm looking for a container class that can map whole ranges of keys to objects - something like std::map, but not only for individual values for the key, but for whole ranges. Example: I...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.