improving a huge double-for cycle

Tim Chase python.list at tim.thechases.com
Tue Sep 23 16:45:12 CEST 2008


km wrote:
> how abt this ?
> 
> N = len(IN)
> for k  in range(N):
>     for j in range(N):
>         if j >= k:                 # or k <= j
>             doSomething()

This has the root problem that the "if" statement is evaluated 
N*N times, which is ugly/slow O(N^2) behavior.  My solution 
managed to reduce it by a constant multiplier, but several folks 
proposed a more elegant O(N) solution which was leaps & bounds 
faster.

-tkc






More information about the Python-list mailing list