Welcome, guest | Sign In | My Account | Store | Cart

Transforms nested loops like <pre>for x in range(width): for y in range(height): do_something(x,y)</pre> into: <pre>for x,y in nest(width, height): do_something(x,y)</pre>

Python, 222 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
import types
from itertools import izip, count

class Looper:
    "superclass for other loopers"
    def __init__(self):
        self.loop_counter = 0

    def next(self):
        self.loop_counter += 1
        if hasattr(self, 'get_next_value'):
            return self.get_next_value()
        else:
            raise Exception('%s has no get_next_value() method' % self)

    def reset(self, arg=None):
        self.loop_counter = 0
        if hasattr(self, 'do_reset'):
            self.do_reset(arg)
            return self.next()

class RangeLooper(Looper):
    "Loop between numeric ranges"
    def __init__(self, a, b=None, c=None):
        Looper.__init__(self)
        if (b==None) and (c==None): # only a passed in
            self.min, self.max, self.step = 0,a,1
        elif c==None: # min/max passed in
            self.min, self.max, self.step = a,b,1
        else:
            self.min, self.max, self.step = a,b,c
        self.value = self.min

    def get_next_value(self):
        result = self.value
        self.value = self.value + self.step
        return result    
    
    def is_finished(self):
        return self.value >= self.max

    def do_reset(self, arg):
        self.value = self.min

class ListLooper(Looper):
    "Loop through items in a list-like object"
    def __init__(self, list):
        Looper.__init__(self)
        self.list = list
        self.position = 0

    def get_next_value(self):
        result = self.list[self.position]
        self.position += 1
        return result

    def is_finished(self):
        return self.position >= len(self.list)

    def do_reset(self, arg):
        self.position = 0
 
class BooleanLooper(Looper):
    "Loop between True/False"
    def __init__(self, value=True):
        Looper.__init__(self)
        self.value = self.orig_value = value

    def get_next_value(self):
        self.value = not self.value
        return not self.value

    def do_reset(self, arg):
        self.value = self.orig_value

    def is_finished(self):
        return self.loop_counter > 1

class CalcField(Looper):
    "Provide a means for a calculated field, based on counters to the left of this one"
    def __init__(self, F, arg):
        Looper.__init__(self)
        
        self.F = F
        self.value = F(arg)

    def get_next_value(self):
        return self.value
    
    def is_finished(self):
        return True

    def do_reset(self, arg):
        self.value = self.F(arg)

def new_looper(a, arg=None):
    """Helper function for nest()
    determines what sort of looper to make given a's type"""
    if isinstance(a,types.TupleType):
        if len(a) == 2:
            return RangeLooper(a[0],a[1])
        elif len(a) == 3:
            return RangeLooper(a[0],a[1],a[2])
    elif isinstance(a, types.BooleanType):
        return BooleanLooper(a)
    elif isinstance(a,types.IntType) or isinstance(a, types.LongType):
        return RangeLooper(a)
    elif isinstance(a, types.StringType) or isinstance(a, types.ListType):
        return ListLooper(a)
    elif isinstance(a, Looper):
        return a
    elif isinstance(a, types.LambdaType):
        return CalcField(a, arg)

def nest(*args):
    """provide nested loop functionality in a generator context
    
    Put simply, it allows you to flatten your nested loops quite considerably..
    instead of:

    for x in range(width):
        for y in range(depth):
            for z in range(height):
                do_something(x,y,z)
    
    you can write:

    for x,y,z in nest(width, depth, height):
        do_something(x,y,z)
    
    Takes a variable number of arguments which can be:
     integer, tuple, list, string, lambda function, or Looper object

    for integer arguments, you get similar functionality to range():
    >>> for x,y in nest(3,3):
    ...     print x,y
    0 0
    0 1
    0 2
    1 0
    1 1
    1 2
    2 0
    2 1
    2 2

    Tuples let you specify the numeric range more precisely
    (2-tuple: min, max / 3-tuple: min, max, step):
    >>> for x,y in nest( (1,4), (10, 40, 10) ):
    ...     print x,y
    1 10
    1 20
    1 30
    2 10
    2 20
    2 30
    3 10
    3 20
    3 30
    
    Lists and strings are handled by pulling consecutive items (or characters) from them
    >>> for i in nest('abc', [2.5, 7, 3]):
    ...     print i
    ('a', 2.5)
    ('a', 7)
    ('a', 3)
    ('b', 2.5)
    ('b', 7)
    ('b', 3)
    ('c', 2.5)
    ('c', 7)
    ('c', 3)
    
    Boolean arguments make a loop variable which flips from True to False, initialised to the value you gave..
    >>> for i in nest(False, False, False):
    ...     print i, i[0] ^ i[1] ^ i[2]
    (False, False, False) False
    (False, False, True) True
    (False, True, False) True
    (False, True, True) False
    (True, False, False) True
    (True, False, True) False
    (True, True, False) False
    (True, True, True) True
    
    Lambda functions provide calculated fields which are only evaluated when it is their turn to increment.
    >>> for x,calc,y in nest((3,5), lambda(x): float(x[0])/10, 3):
    ...     print x, calc, y
    3 0.3 0
    3 0.3 1
    3 0.3 2
    4 0.4 0
    4 0.4 1
    4 0.4 2
    """
    n_levels = len(args)
    loopers = [None] * n_levels
    counters = []
    for i,a in izip(count(), args):
        loopers[i] = new_looper(a, counters)
        counters.append(loopers[i].next())
            
    def inc_counters(n=n_levels-1):
        "Increment counters, rightmost first"
        if n < 0:
            raise StopIteration
        if loopers[n].is_finished():
            inc_counters(n-1)
            counters[n] = loopers[n].reset(arg=counters[:n])
        else:
            counters[n] = loopers[n].next()
                
    while 1:
        yield tuple(counters)
        inc_counters()

def _test():
    import doctest
    doctest.testmod()

if __name__ == "__main__":
    _test()

Using nest(), you lose the ability to run code between the termination of one loop and the termination of its enclosing loop. However by passing a lambda function to nest() you can have loop variables which are calculated from the current list counter values to the left of the calculated field, which is fairly equivalent to initialising a variable to some value dependent on an enclosing loop's variable, prior to entering a new nested loop.

so while:

<pre>for x in range(width): color = rgb(width/float(x),0,0) for y in range(height): set_pixel(x,y,color)</pre>

is expressible as:

<pre>for x,color,y in nest(width, lambda(a): rgb(width/float(a[0]),0,0), height): set_pixel(x,y,color)</pre>

something like the following would not be:

<pre>hist = {} for w in ['inconsequential', 'iterators', 'irritate']: for l in w: if hist.has_key(l): hist[l] += 1 else: hist[l] = 1 print hist</pre>

because of the "print hist" line (actually also because of the "for l in w:" line, see below) - although the value of hist would be the same at the end of the loop's run

the bit about "for l in w:" is tricky because it iterates through the characters of a loop counter variable, which is not necessarily known when you first call nest().. of course you can get round it, by subclassing Looper():

<pre>class MyLooper(Looper): def __init__(self, F, arg): Looper.__init__(self) self.F = F self.value = F(arg) def get_next_value(self): return self.value def do_reset(self, arg): self.value = F(arg) def is_finished(self, arg): return True

hist = {} old_w = None for w,l in nest(['inconsequential', 'iterators', 'irritate'], MyLooper(lambda(x): x[0], ['inconsequential']) ): if old_w == None: old_w = w

if l not in hist:
    hist[l] = 0
    hist[l] += 1

if old_w <> w:
    print hist</pre>

7 comments

Michael Spencer 15 years, 10 months ago  # | flag

Seems like overkill. I normally use something like the following for cartesian products:

def nest(*iterables):
    def _nest(outer, inner):
        for outer_item in outer:
            if not isinstance(outer_item, tuple):
                outer_item = (outer_item,)
            for inner_item in inner:
                yield outer_item + (inner_item,)
    return reduce(_nest, iterables)

 >>> list(nest(range(2), range(2), range(2)))
 [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
runsun pan 15 years, 10 months ago  # | flag

why bother? >>> [(i,j,k) for i in range(2) for j in range(2) for k in range(2)]

[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

runsun pan 15 years, 10 months ago  # | flag

Use list comprehension ? It seems to me that a task like :

for x in range(width):

    for y in range(height):

        do_something(x,y)

can be accomplished with simple list comprehension:

[ do_somthing(x,y) for x in range(width) for y in range(height) ]

that is, one-liner compared to this long recipe.

Zoran Isailovski 15 years, 10 months ago  # | flag

presumably an improper use of list comprehensions. Beware that

[ do_somthing(x,y) for x in range(width) for y in range(height) ]

creates a list of width*height None's, which consumes (perhaps a significant amout of) memory with no benefit at all.

List comprehensions are meant to ease list construction, not to squeeze for loops.

runsun pan 15 years, 10 months ago  # | flag

That's true.

The list comprehension example that I posted was just to demonstrate
the intrinsic capability of python to loop thru nested ranges. In
the newer python this "for-x-for-y" thingy doesn't need to be in a
list. Instead, it can be in ( ) to represent a generator.

Using the examples shown in this recipes:

    >>> for x,y in nest(3,3):
    ...     print x,y

could be:

    >>> for x,y in ( (x,y) for x in range(3) for y in range(3)):
    ...     print x,y

and

    >>> for x,y in nest( (1,4), (10, 40, 10) ):
    ...     print x,y

could be:

    >>> for x,y in ( (x,y) for x in range(1,4) for y in range(10,40,10)):
    ...     print x,y


In these cases this recipe(nest) does make it shorter but with a
trade-in of having an extra module to import and an extra function
api to remember. This is probably upto personal tastes, i guess.

In situations when conditional operations are in need, like the
following case:

    >>> for x,calc,y in nest((3,5), lambda(x): float(x[0])/10, 3):
    ...     print x, calc, y

the intrinsic "for-x-for-y" approach is actually, IMO, much more
readable:

    >>> for x,calc,y in ( (x,x/10.0,y) for x in range(3,5) for y in range(3) ):
...     print x, calc, y
Scott Lees (author) 15 years, 7 months ago  # | flag

Yep, kinda see what you all mean.. This recipe bacically came from a requirement to allow nested loops of non-specific depth (ie to be determined at run-time), as well as slightly more trackable in-place modification of the lists beings iterated over.. (permutations based countdown number game solver)

I agree with pretty much everything everybody said so far though, it's a bit unwieldy for everyday use, and most of what it gives you, you already get from list comprehensions, generators, and simple for-loops

in fact, it would've been rather less unwieldy (hmm. more wieldy?) if I'd posted it in its original form (just the list-based iterator iirc).. I added all that other crap to show how wonderfully versatile it all was :/

Gail Gong 13 years, 6 months ago  # | flag

This is almost what I want. I have a sample of families. For each family, I would like to do a calculation that involves M nested for loops where M is the size of the family. Families come in different sizes so each family requires a different number of nested for loops. I want to do something like this: for tuple in nest(2,2,2...2): do something on tuple

where the number of 2's in the argument of nest changes with family size. Any ideas?

Created by Scott Lees on Wed, 1 Feb 2006 (PSF)
Python recipes (4591)
Scott Lees's recipes (1)

Required Modules

Other Information and Tasks