On Feb 1, 11:23 am, Thomas Pani <[EMAIL PROTECTED]> wrote:
> Arnaud Delobelle wrote:
>
> > This is definitely the best way:
>
> > from itertools import chain
>
> > def overlaps(lst):
> > bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)))
> > inside = {}
> > for x, i in sorted(bounds):
> > if inside.pop(i, None) is None:
> > for j, y in inside.iteritems():
> > if y != x: yield i, j
> > inside[i] = x
>
> Why not just
>
> def overlaps(lst):
> for i,x in enumerate(lst):
> for j,y in enumerate(lst):
> if i != j and x[1] > y[2] > x[2]:
> yield i,j
>
> It's still n^2. Or am I missing something?
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).
PS: the way I build 'bounds' is awkward.
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
