Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   nested for loop (http://www.velocityreviews.com/forums/t330763-nested-for-loop.html)

 Wolfgang Buechel 05-10-2004 09:30 PM

nested for loop

Hi,

I want to iterate over all 2x2 matrices with elements in range 0..25
(crypto-stuff).

To produce them, first I wrote a fourfold nested for loop:

M=26
for a in range(M):
for b in range (M):
for c in range (M):
for d in range (M):
matr = [[a,b],[c,d]]
(dosomething)

Then I had a look in comp.lang.python and found:

for (a,b,c,d) in [(x,y,z,t) for x in range(M)
for y in range(M)
for z in range(M)
for t in range(M)] :
matr = [[a,b],[c,d]]

Is there a shorter (and probably, with respect to exec time, faster)
way to write such a 4for loop?
(I want to scan 3x3, 4x4 matrices too (;-)

-- Wolfgang

 Tor Iver Wilhelmsen 05-10-2004 09:52 PM

Re: nested for loop

wjb131@web.de (Wolfgang Buechel) writes:

> for (a,b,c,d) in [(x,y,z,t) for x in range(M)
> for y in range(M)
> for z in range(M)
> for t in range(M)] :
> matr = [[a,b],[c,d]]

Try assigning range(M) to a variable instead of creating four copies
of it. For larger ranges, experiment using xrange instead.

 Peter Hansen 05-10-2004 11:51 PM

Re: nested for loop

Wolfgang Buechel wrote:

> I want to iterate over all 2x2 matrices with elements in range 0..25
> (crypto-stuff).
>
> To produce them, first I wrote a fourfold nested for loop:
>
> M=26
> for a in range(M):
> for b in range (M):
> for c in range (M):
> for d in range (M):
> matr = [[a,b],[c,d]]
> (dosomething)
>
> Then I had a look in comp.lang.python and found:
>
>
> for (a,b,c,d) in [(x,y,z,t) for x in range(M)
> for y in range(M)
> for z in range(M)
> for t in range(M)] :
> matr = [[a,b],[c,d]]
>
> Is there a shorter (and probably, with respect to exec time, faster)
> way to write such a 4for loop?

Hmm... why would you want something shorter, as it would
probably be less readable? Also, how fast do you need it
to run, or how many times faster than the above would you
like it to run?

(The second one is a facetious question... the first is
more serious. In effect: what's wrong with what you have?)

-Peter

 Terry Reedy 05-11-2004 01:03 AM

Re: nested for loop

"Wolfgang Buechel" <wjb131@web.de> wrote in message
> Hi,
>
> I want to iterate over all 2x2 matrices with elements in range 0..25
> (crypto-stuff).
>
> To produce them, first I wrote a fourfold nested for loop:
>
> M=26
> for a in range(M):
> for b in range (M):
> for c in range (M):
> for d in range (M):
> matr = [[a,b],[c,d]]
> (dosomething)

This is completely clear and space efficient.

> Then I had a look in comp.lang.python and found:

Oh dear...

> for (a,b,c,d) in [(x,y,z,t) for x in range(M)
> for y in range(M)
> for z in range(M)
> for t in range(M)] :
> matr = [[a,b],[c,d]]

This is less clear. It took me about 10 seconds (versus 1) to see as
equivalent. It produces a list with M**4 elements that you don't actually
need and soon throw away.

> Is there a shorter (and probably, with respect to exec time, faster)
> way to write such a 4for loop?

Write a C extension, maybe with Pyrex. However, an hour of your time is
worth lots of hours of PC time. But for a million runs, it might be worth
it.

Terry J. Reedy

 Sean Ross 05-11-2004 02:10 AM

Re: nested for loop

"Wolfgang Buechel" <wjb131@web.de> wrote in message
> Hi,
>
> I want to iterate over all 2x2 matrices with elements in range 0..25
> (crypto-stuff).

[snip]
> Is there a shorter (and probably, with respect to exec time, faster)
> way to write such a 4for loop?
> (I want to scan 3x3, 4x4 matrices too (;-)
>
> -- Wolfgang

Hi.

The following code isn't necessarily shorter or faster (or more readable),
but it's a bit more general:

# slightly modified code from
http://twistedmatrix.com/wiki/python/PostYourCode
def sequences(n, things):
"generates sequences of n items from a set of things"
if n == 0:
yield []
else:
for x in things:
for y in sequences(n-1, things):
yield [x] + y

def nXn_matrices(n, elements):
"generates nXn matrices from elements"
for s in sequences(n*n, elements):
yield [s[i*n:(i+1)*n] for i in xrange(n)]

# we'll try it over a small range ...
M = 3
for m in nXn_matrices(2, range(M)):
print m

Output:
[[0, 0], [0, 0]]
[[0, 0], [0, 1]]
[[0, 0], [0, 2]]
[[0, 0], [1, 0]]
[[0, 0], [1, 1]]
[[0, 0], [1, 2]]
[[0, 0], [2, 0]]
....
....
[[2, 2], [2, 0]]
[[2, 2], [2, 1]]
[[2, 2], [2, 2]]

# now 3X3 ... this takes a _l_o_n_g_ time ...
M = 3
for m in nXn_matrices(3,range(M)):
print m

Output:
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
[[0, 0, 0], [0, 0, 0], [0, 0, 1]]
[[0, 0, 0], [0, 0, 0], [0, 0, 2]]
[[0, 0, 0], [0, 0, 0], [0, 1, 0]]
[[0, 0, 0], [0, 0, 0], [0, 1, 1]]
[[0, 0, 0], [0, 0, 0], [0, 1, 2]]
....
....
[[2, 2, 2], [2, 2, 2], [2, 1, 0]]
[[2, 2, 2], [2, 2, 2], [2, 1, 1]]
[[2, 2, 2], [2, 2, 2], [2, 1, 2]]
[[2, 2, 2], [2, 2, 2], [2, 2, 0]]
[[2, 2, 2], [2, 2, 2], [2, 2, 1]]
[[2, 2, 2], [2, 2, 2], [2, 2, 2]]

I'm believe there are several opportunities for optimization both in the
code and in the algorithm (for instance, it may be possible to take
advantage of repetition in the sub-matrices), but I won't be trying that
now.

Good luck with what you're doing,
Sean

 Sean Ross 05-11-2004 03:09 AM

Re: nested for loop

"Sean Ross" <sross@connectmail.carleton.ca> wrote in message
news:VDWnc.21679\$FH5.581779@news20.bellglobal.com. ..
[snip]
> # slightly modified code from
> http://twistedmatrix.com/wiki/python/PostYourCode
> def sequences(n, things):
> "generates sequences of n items from a set of things"
> if n == 0:
> yield []
> else:
> for x in things:
> for y in sequences(n-1, things):
> yield [x] + y
>
> def nXn_matrices(n, elements):
> "generates nXn matrices from elements"
> for s in sequences(n*n, elements):
> yield [s[i*n:(i+1)*n] for i in xrange(n)]

[snip]
> [I] believe there are several opportunities for optimization both in the
> code and in the algorithm (for instance, it may be possible to take
> advantage of repetition in the sub-matrices), but I won't be trying that
> now.

Looks like I'll be trying it now after all:

def nXn_matrices2(n, elements):
for m in sequences(n, list(sequences(n, elements))):
yield m

This is slightly faster than the first version, but it has more overhead
since it builds a list of the submatrices. That could be problem. It can
probably be avoided, but I haven't figured out how to do it just yet. We'll
see what happens.

Sean

 Anton Vredegoor 05-11-2004 12:34 PM

Re: nested for loop

wjb131@web.de (Wolfgang Buechel) wrote:

>I want to iterate over all 2x2 matrices with elements in range 0..25
>(crypto-stuff).
>
>To produce them, first I wrote a fourfold nested for loop:
>
>M=26
> for a in range(M):
> for b in range (M):
> for c in range (M):
> for d in range (M):
> matr = [[a,b],[c,d]]
> (dosomething)

[snip]

>Is there a shorter (and probably, with respect to exec time, faster)
>way to write such a 4for loop?
>(I want to scan 3x3, 4x4 matrices too (;-)

This question is very much related to the one in a thread below here
(titled "Inverse of int(s, base)?"). In fact with a small adaptation
that code can produce this kind of matrices:

from itertools import islice

def tobase(i,base,digits):
R = []
for j in xrange(digits):
i,k = divmod(i,base)
R.append(k)
R.reverse()
return R

def as_matrix(R,rows,cols):
it = iter(R)
return[list(islice(it,cols)) for i in xrange(rows)]

def test():
for i in range(10):
R = tobase(i,25,6)
print as_matrix(R,3,2)

if __name__=='__main__':
test()

Anton

 Wolfgang Buechel 05-23-2004 08:28 AM

Re: nested for loop

wjb131@web.de (Wolfgang Buechel) wrote in message news:<4629559b.0405101330.286ddb32@posting.google. com>...
> Hi,
>
> I want to iterate over all 2x2 matrices with elements in range 0..25
> (crypto-stuff).

Try generators (new in Python 2.3.3).
There is an example you can/must adapt:

(PythonPath)/Lib/test/test_generators.py
def conjoin()

and in the whatsnew-documentation:

http://www.python.org/doc/2.3.3/what...enerators.html

--W.

 Dan Bishop 05-23-2004 10:07 PM

Re: nested for loop

wjb131@web.de (Wolfgang Buechel) wrote in message news:<4629559b.0405101330.286ddb32@posting.google. com>...
> Hi,
>
> I want to iterate over all 2x2 matrices with elements in range 0..25
> (crypto-stuff).
>
> To produce them, first I wrote a fourfold nested for loop:

....
> Then I had a look in comp.lang.python and found:
>
>
> for (a,b,c,d) in [(x,y,z,t) for x in range(M)
> for y in range(M)
> for z in range(M)
> for t in range(M)] :
> matr = [[a,b],[c,d]]

This may be shorter, but it's slower. Your old code took "only" 1.5
seconds to run on this computer, but the new way takes 3.5 seconds.

What you *can* do to make your code faster (if you don't change matr
once it's created) is to precompute the 676 possible matrix rows.

ELEMENT_RANGE = range(26)
MATRIX_ROWS = [[x, y] for x in ELEMENT_RANGE
for y in ELEMENT_RANGE]
for row1 in MATRIX_ROWS:
for row2 in MATRIX_ROWS:
matr = [row1, row2]

That takes only 532 ms -- almost 3 times faster than the original.

 Terry Reedy 05-23-2004 11:35 PM

Re: nested for loop

"Dan Bishop" <danb_83@yahoo.com> wrote in message
> What you *can* do to make your code faster (if you don't change matr
> once it's created) is to precompute the 676 possible matrix rows.
>
> ELEMENT_RANGE = range(26)
> MATRIX_ROWS = [[x, y] for x in ELEMENT_RANGE
> for y in ELEMENT_RANGE]
> for row1 in MATRIX_ROWS:
> for row2 in MATRIX_ROWS:
> matr = [row1, row2]
>
> That takes only 532 ms -- almost 3 times faster than the original.

Cute. While I am quite familiar with and have experience applying the
principle of computing once instead of multiple times, I missed its
application here.

tjr

All times are GMT. The time now is 08:03 AM.