How to identify which numbers in a list are within each others' range
Arnaud Delobelle
arnodel at googlemail.com
Fri Feb 1 21:16:23 CET 2008
On Feb 1, 2:44 pm, "Neil Cerutti" <mr.ceru... at gmail.com> wrote:
> On Feb 1, 2008 8:28 AM, Arnaud Delobelle <arno... at googlemail.com> wrote:
>
> > Yours is O(n^2) and \Omega(n^2). I think mine is O(max(c, nlogn))
> > (assuming constant time access for dictionaries, but 'inside' could be
> > replaced with a list) where c is the number of overlaps. I'll try to
> > post a proof later (if it's true!). So if we are in a situation where
> > overlaps are rare, it is in practice O(nlogn).
>
> Here's another contender, basically the same as yours, but spelled
> without iterators.
>
> def overlaps(eranges):
> """Determine, from a list of numbers and a +/- range of uncertainty, which
> number ranges overlap each other. Return the overlapping range indexes as
> a list of overlapping pairs.
>
> >>> sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3))))
> [(0, 3), (1, 2)]
> """
> d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)]
> d.sort()
> rv = []
> x = 0
> while x < len(d):
> minx, maxx, ix = d[x]
> y = x+1
> while y < len(d):
> miny, maxy, iy = d[y]
> if miny < maxx:
> rv.append((ix, iy) if ix < iy else (iy, ix))
> else:
> break
> y += 1
> x += 1
> return rv
The total number of iterations is 1+2+...+n = n(n+1)/2 (when n is the
number of intervals) so this has quadratic behaviour regardless of
input. See my other post for a 'detailed' analysis of my solution.
--
Arnaud
More information about the Python-list
mailing list