Need some help speeding up this loop

[Marc 'BlackJack' Rintsch]

On Wed, 29 Oct 2008 19:24:32 -0700, erikcw wrote:

> I'm trying to write a loop that will build a list of "template strings".
> 
> My current implementation is *really slow*.  It took 15 minutes to
> finish. (final len(list) was about 16k entries.)

What is `list` here?  Do you mean ``len(templates)``?

> templates = []
> for c in combinations:
>     if len(states):
>         for state in states:
>             if type(geo) is City:
>                 cities = state.city_set.all()
>             else:
>                 cities = geo
>             for city in cities:
>                 if type(city) is City:
>                     city = city.city
>                 templates.append(c.template.replace('{{ city }}',
> city))
>             templates.append(c.template) #just in case there are no
> cities
>             templates = [k.replace('{{ state }}',
> state.state).replace('{{ state_abbr }}', state.abbreviation) for k in
> templates]

It seems you are iterating over *all* accumulated templates so far, over 
and over again, even those which don't have those place holders anymore.  
Looks like the source of quadratic runtime for me.

Ciao,
	Marc 'BlackJack' Rintsch