improving a huge double-for cycle

[J. Cliff Dyer]

On Thu, 2008-09-18 at 07:57 -0500, Tim Chase wrote:
> > Code: Select all
> >     for i in range(len(IN)): #scan all elements of the list IN
> >       for j in range(len(IN)):
> >         if i <> j:
> >          if IN[i].coordinates[0] == IN[j].coordinates[0]:
> >            if IN[i].coordinates[1] == IN[j].coordinates[1]:
> >               SN.append(IN[i].label)
> > 
> > 

> Such changes might look something like
> 
>    for i in xrange(len(IN)):
>      for j in xrange(i+1, len(IN)):
>        if IN[i].coordinates == IN[j].coordinates:
>          SN.append(IN[i].label)

If you aren't checking j values less than i, you might want to do both

           SN.append(IN[i].label)
           SN.append(IN[j].label)

on the same pass.


> If my college algorithms memory serves me sufficiently, this 
> reduces your O(N^2) to O(N log N) which will garner you some 
> decent time savings.
> 
> -tkc
> 
> 
> --
> http://mail.python.org/mailman/listinfo/python-list
>