Need some help speeding up this loop

[erikcw]

Hi all,

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.)

#combinations = 12 small template strings ie "{{ city }},
{{ state }}..."
#states = either a django model or a list of 50 states
#cities = either a django model of 400 cities or a smaller list of
cities.

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]
    elif len(geo):
        for city in geo:
            templates.append(c.template.replace('{{ city }}', city))
    else:
        #no cities or states so add roots
        templates.append(c.template)

The final output needs to be a list of the templates combined with all
the states and cities (some templates will only have the city, some
only the state).

Any ideas how I can optimize this?

Thanks!