improving a huge double-for cycle

[Bruno Desthuilliers]

Harald Luessen a écrit :
(snip)
> I did not test the syntax,
> but here is an idea with sorted lists.
> It should be O(NlogN).
> 
> def sk(x):
>     return x.coordinates[0]
> 
> IN.sort(key=sk)
> for i in xrange(len(IN)):
>     for j in xrange(i+1, len(IN)):
>         if IN[i].coordinates[0] == IN[j].coordinates[0]:
>             if IN[i].coordinates[1] == IN[j].coordinates[1]:
>                 SN.append(IN[i].label)
>         else:
>             break

The syntax is ok. Not the results, or so it seems (cf my other post in 
this thread). But you still get a good point for noticing the redundant 
tests in the inner loop !-)