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!

 

[Marc 'BlackJack' Rintsch]

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

 

[Arnaud Delobelle]

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]

The line above does a lot of unnecessary work as you iterate over lots
of templates which have already been completely substituted.

    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!

I would suggest this (untested):

def template_replace(template, values):
for var, val in values.iteritems():
template = template.replace('{{ %s }}' % var, val)
return template

templates = []
for c in combinations:
if len(states):
for state in states:
values = { 'state': state.state,
'state_abbr': state.abbreviation }
#just in case there are no cities :
templates.append(template_replace(c.template, values)
if type(geo) is City:
cities = state.city_set.all()
else:
cities = geo
for city in cities:
if type(city) is City:
values['city'] = city.city
# Do all the replacing in one go:
templates.append(template_replace(c.template,
values))
elif len(geo):
for city in geo:
templates.append(template_replace(c.template,
{'city':city}))
else:
#no cities or states so add roots
templates.append(c.template)

HTH

Even better would be to iterate over states, then cities, then only
templates.