Need some help speeding up this loop

Arnaud Delobelle arnodel at googlemail.com
Thu Oct 30 11:01:50 CET 2008


On Oct 30, 2:24 am, erikcw <erikwickst... at gmail.com> wrote:
> 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



More information about the Python-list mailing list