my loop is too slow

[Michael P. Reilly]

Johan Wouters <johanw at easics.be> wrote:
: SC Zhong wrote:
:> 
:> I tried to learn and use python a week ago, and wrote
:> a small application.  When it run the loop:
:> 
:>         for k in range(dimension):
:>                 for i in range(dimension):
:>                         for j in range(dimension):
:>                                 for h in range(dimension):
:>                                         a[k,i]=a[k,i]+c[k,h]*c[k,j]*\
:>                                                 f[j,i]*f[i,h]
:> 
:> it took very long time (may be 10 hours in my HP workstation). dimension
:> is 142 and a,c,f are all complex.

Each time through each loop a list of length 142 is created.  This
means that for the h loop alone a new list is created 2863288 times.
loop  #created  calculation
   k         1  pow(142, 0)
   i       142  pow(142, 1)
   j     20164  pow(142, 2)
   h   2863288  pow(142, 3)

:> I do not want to waste the other part of the program which processing text
:> file and rewrite the whole program in C or Fortran.  Is there ways to speed
:> the above up?
:> 
:> Thanks a lot.
:> SC CHUNG

: One thing would be to predefine the range(dimension) part like:

: dim_range
: for k in dim_range:
:   for i in dim_range:
:     for j in dim_range:
:       for h in dim_range:
:          a[k,i]=a[k,i]+c[k,h]*c[k,j]*f[j,i]*f[i,h]

: This will save you about 406*10E6 list creations.

There is also xrange(n) which returns an interator object instead of
constructing a new list on each call.  This is more useful if you have
different dimensions for each index.  Or even if they are not, you could
create different pre-defined ranges like Johan suggests.

: Next thing to notice is the costly lookup of some data items. For instance,
: c[k,j], f[j,i], a[k,i] Move these list searches up in the loops like:

: dim_range
: for k in dim_range:
:   for i in dim_range:
:     a_ki = a[k,i]
:     for j in dim_range:
:       c_kj = c[k,j]
:       f_ji = f[j,i]
:       for h in dim_range:
:          a_ki=a_ki+c[k,h]*c_kj*f_ji*f[i,h]
:     a[k,i]=a_ki

: I hope this gives you an idea on how to further improve code speed (eg. c_kj*f_ji=constant in the h-loop)
: Maybe some "map" like construct will give you a faster inner loop

_Usually_ (but not always), Python's for loop is indeed faster than map.
Chalk this up to Guido's mild dislike of some of the functional programming
commands.

I haven't ever needed to look into it, but it sounds like some of the
features of NumPy might help you.  I'm sure that someone who knows more
about it can help more. :)

  -Arcege