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]

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

[Arnaud Delobelle]

On Oct 30, 2:24*am, erikcw <[e-mail]:

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.

--
Arnaud