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.
--
http://mail.python.org/mailman/listinfo/python-list
