nested for loop

Discussion in 'Python' started by Wolfgang Buechel, May 10, 2004.

  1. 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
     
    Wolfgang Buechel, May 10, 2004
    #1
    1. Advertising

  2. (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.
     
    Tor Iver Wilhelmsen, May 10, 2004
    #2
    1. Advertising

  3. Wolfgang Buechel

    Peter Hansen Guest

    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
     
    Peter Hansen, May 11, 2004
    #3
  4. Wolfgang Buechel

    Terry Reedy Guest

    "Wolfgang Buechel" <> wrote in message
    news:...
    > 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
     
    Terry Reedy, May 11, 2004
    #4
  5. Wolfgang Buechel

    Sean Ross Guest

    "Wolfgang Buechel" <> wrote in message
    news:...
    > 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, May 11, 2004
    #5
  6. Wolfgang Buechel

    Sean Ross Guest

    "Sean Ross" <> wrote in message
    news:VDWnc.21679$...
    [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]
    > 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
     
    Sean Ross, May 11, 2004
    #6
  7. (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
     
    Anton Vredegoor, May 11, 2004
    #7
  8. (Wolfgang Buechel) wrote in message news:<>...
    > 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:
    Look at your Python installation:

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

    and in the whatsnew-documentation:

    http://www.python.org/doc/2.3.3/whatsnew/section-generators.html

    --W.
     
    Wolfgang Buechel, May 23, 2004
    #8
  9. Wolfgang Buechel

    Dan Bishop Guest

    (Wolfgang Buechel) wrote in message news:<>...
    > 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.
     
    Dan Bishop, May 23, 2004
    #9
  10. Wolfgang Buechel

    Terry Reedy Guest

    "Dan Bishop" <> wrote in message
    news:...
    > 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
     
    Terry Reedy, May 24, 2004
    #10
  11. Wolfgang Buechel

    Peter Otten Guest

    Dan Bishop wrote:

    > 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.


    Nice. Another speed gain (from 435 to 246ms on my machine) is in for you if
    you use tuples instead of lists. And if you allow for somewhat less elegant
    code that builds on your recipe,

    from itertools import izip, repeat
    ELEMENT_RANGE = range(26)
    MATRIX_ROWS = [(x, y) for x in ELEMENT_RANGE
    for y in ELEMENT_RANGE]
    for row in MATRIX_ROWS:
    for matr in izip(repeat(row), MATRIX_ROWS):
    pass

    you can bring that down to 138ms.

    For the record: the straightforward solution (the original with tuples and
    range() factored out)

    r = range(26)
    for a in r:
    for b in r:
    for c in r:
    for d in r:
    matr = ((a,b),(c,d))

    takes 478ms. The "improved" variant is evil performance-wise (1598ms):

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

    It might be interesting how much this can be improved with 2.4's generator
    expressions.

    Peter
     
    Peter Otten, May 24, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russ Perry Jr
    Replies:
    2
    Views:
    4,237
    Russ Perry Jr
    Aug 20, 2004
  2. Chad E. Dollins
    Replies:
    3
    Views:
    673
    Kai-Uwe Bux
    Nov 8, 2005
  3. request@no_spam.com
    Replies:
    5
    Views:
    449
  4. Ultrus
    Replies:
    3
    Views:
    398
    Stefan Behnel
    Jul 9, 2007
  5. Isaac Won
    Replies:
    9
    Views:
    419
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page