improving a huge double-for cycle

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Thu Sep 18 15:13:39 CEST 2008


Skip:
>     indexes = range(len(IN))
>     for i in indexes: #scan all elements of the list IN
>       for j in indexes:

Nope, use xrange in both situations, and save a list.


Tim Chase:
>    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 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.

That's O(n^2) still, it's just half matrix, a triangle.

Bye,
bearophile



More information about the Python-list mailing list