Re: how to make a generator use the last yielded value when it regains control
Lonnie Princehouse wrote: Here's my take on the thing. It only prints one term, though. http://www.magicpeacefarm.com/lonnie/code/morris.py.html (a bit too long to post) excerpt : def morris(seed, n): ... if n == 1: return seed else: return length_encode(morris(seed,n-1)) What's wrong with the following ? def morris(seed,n) : ... for k in xrange(n-1) : seed=length_encode(seed) return seed or even def morris(seed,n) : return reduce(lambda x,y:y(x),n*[length_encode],seed) I'd defend using recursion when it allows a more concise expression of an algorithm, but not in other cases. Mmmhhh, btw, strangely, it looks like a hole in the library that you can't write eg morris= lambda seed,n: reduce(operator.__rcall__,n*[length_encode],seed) -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
What's wrong with the following ? def morris(seed,n) : ... for k in xrange(n-1) : seed=length_encode(seed) return seed Nothing's wrong with it. I happen to think the recursive version is more elegant, but that's just me ;-) -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Em Seg, 2006-04-10 às 10:05 -0700, Lonnie Princehouse escreveu: I happen to think the recursive version is more elegant, but that's just me ;-) It may be elegant, but it's not efficient when you talk about Python. Method calls are expensive: $ python2.4 -mtimeit 'pass' 1000 loops, best of 3: 0.0585 usec per loop $ python2.4 -mtimeit -s 'def x(): pass' 'x()' 100 loops, best of 3: 0.291 usec per loop $ calc 0.291/0.0585 ~4.97435897435897435897 $ calc 0.291-0.0585 0.2325 This happens because of the dynamic nature of Python and its lack of tail call optimization. IOW, avoid recursive methods when possible (I usually write those for the first version of a method then rethink it using a non-recursive approach), specially if they are part of a hot spot. -- Felipe. -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
In general, you're right - if speed is a concern, loops should be used instead of recursion in Python when possible. In this case, the recursive overhead is insignificant compared to the expense of iterating over the sequence at every iteration. By the time there are 70 stack frames of recursion (i.e. not much), the sequence is more than 170 million elements long. -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote: Ben Cartwright wrote: Definitely go for (1). The Morris sequence is a great candidate to implement as a generator. As a generator, it will be more flexible and efficient than (2). Actually I was just thinking about this and it seems like, at least for my purpose (to simply return a list of numbers), I don't need a generator. My understanding of a generator is that you do something to each yielded value before returning to the generator (so that you might not return at all), but since I'm not handling the individual numbers, just getting a list, it seems I don't need them to be yielded. Of course, a generator would allow the process to be done over and over, I suppose, which is what I wanted, I just couldn't figure out how to keep using the new values. itertools.groupby makes this very straightforward: from itertools import groupby ... def lookandsay(seed): ... seed = str(seed) ... while 1: ... seed = .join(%s%s % (len(list(group)), item) ... for item, group in groupby(seed)) ... yield seed ... seq = lookandsay(1) seq.next() '11' seq.next() '21' seq.next() '1211' seq.next() '111221' seq.next() '312211' If you want to get just part of the infinite series, use itertools.islice: from itertools import islice list(islice(lookandsay(1),10)) ['11', '21', '1211', '111221', '312211', '13112221', '1113213211', '31131211131221', '13211311123113112211', '11131221133112132113212221'] list(islice(lookandsay(1),10,20)) ['3113112221232112111312211312113211', '1321132132111213122112311311222113111221131221', '11131221131211131231121113112221121321132132211331222113112211', '311311222113111231131112132112311321322112111312211312111322212311322113212221', '132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211', '11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221', '31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211', '1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221', '11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211', '311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221'] HTH Michael -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Michael Spencer wrote: itertools.groupby makes this very straightforward: I was considering this function, but then it seemed like it was only used for determing consecutive numbers like 1, 2, 3 -- not consecutive equivalent numbers like 1, 1, 1. But is that not right? -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote: Michael Spencer wrote: itertools.groupby makes this very straightforward: I was considering this function, but then it seemed like it was only used for determing consecutive numbers like 1, 2, 3 -- not consecutive equivalent numbers like 1, 1, 1. But is that not right? data = [1, 1, 1, 2, 2, 3, 4, 4, 3, 2, 2, 1, 1, 2, 2,4, 2, 2] from itertools import groupby for k, g in groupby( data ): print k, list(g) 1 [1, 1, 1] 2 [2, 2] 3 [3] 4 [4, 4] 3 [3] 2 [2, 2] 1 [1, 1] 2 [2, 2] 4 [4] 2 [2, 2] for k, g in groupby( data, lambda x: x2 ): print k, list(g) True [1, 1, 1] False [2, 2, 3, 4, 4, 3, 2, 2] True [1, 1] False [2, 2, 4, 2, 2] Gerard -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote:
Michael Spencer wrote:
itertools.groupby makes this very straightforward:
I was considering this function, but then it seemed like it was only
used for determing consecutive numbers like 1, 2, 3 -- not consecutive
equivalent numbers like 1, 1, 1. But is that not right?
With one argument, groupby assembles groups of equal consecutive elements:
list((key, list(group)) for key, group in groupby(AAABBCAAA))
[('A', ['A', 'A', 'A']), ('B', ['B', 'B']), ('C', ['C']), ('A', ['A', 'A',
'A'])]
With a second keyfunc argument, groupby assembles groups where keyfunc(element)
is equal for consecutive elements
list((key, list(group)) for key, group in groupby(AAAaaaAAA,str.isupper))
[(True, ['A', 'A', 'A']), (False, ['a', 'a', 'a']), (True, ['A', 'A', 'A'])]
HTH
Michael
--
http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Gerard Flanagan wrote: John Salerno wrote: Michael Spencer wrote: itertools.groupby makes this very straightforward: I was considering this function, but then it seemed like it was only used for determing consecutive numbers like 1, 2, 3 -- not consecutive equivalent numbers like 1, 1, 1. But is that not right? data = [1, 1, 1, 2, 2, 3, 4, 4, 3, 2, 2, 1, 1, 2, 2,4, 2, 2] from itertools import groupby for k, g in groupby( data ): print k, list(g) 1 [1, 1, 1] 2 [2, 2] 3 [3] 4 [4, 4] 3 [3] 2 [2, 2] 1 [1, 1] 2 [2, 2] 4 [4] 2 [2, 2] for k, g in groupby( data, lambda x: x2 ): print k, list(g) True [1, 1, 1] False [2, 2, 3, 4, 4, 3, 2, 2] True [1, 1] False [2, 2, 4, 2, 2] Gerard Interesting. After following along with the doc example, it seemed like I had to do complicated stuff with the keys parameter, and I kind of lost track of it all. -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Here's my take on the thing. It only prints one term, though. http://www.magicpeacefarm.com/lonnie/code/morris.py.html (a bit too long to post) -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
just couldn't help taking the bait...
def morris(seed) :
m = morris('3447221')
m.next()
'1324172211'
m.next()
'1113121411172221'
m.next()
'31131112111431173211'
assert isinstance(seed,basestring) and seed.isdigit(),bad seed
def itially(z) :
feedback.z = z
while True :
yield feedback.z
def feedback(gen) :
while True :
feedback.z = gen.next()
yield feedback.z
def morrisify(number) :
from itertools import groupby
for digit,sequence in groupby(number) :
yield str(len(tuple(sequence)))
yield digit
return feedback(''.join(morrisify(number))
for number in itially(seed))
--
http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Lonnie Princehouse wrote: Here's my take on the thing. It only prints one term, though. http://www.magicpeacefarm.com/lonnie/code/morris.py.html (a bit too long to post) yikes, scary! :) there was always the hint that using itertools might be helpful, as you guys are doing, but i could never quite figure out how, but looking at these alternate methods is definitely helpful -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote: 1. repeat indefinitely and have the number of times controlled elsewhere in the program (e.g., use the morris() generator in a for loop and use that context to tell it when to stop) 2. just make it a function that takes a second argument, that being the number of times you want it to repeat itself and create numbers in the sequence Well, I suppose I could just do: num = 1 for x in range(some_limit): num = morris(num) print num, But that isn't as much of a challenge as the other two options. :) I'd like the function to do all the work of returning multiple numbers (which probably means that option 1 isn't the best either) -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote: 2. just make it a function that takes a second argument, that being the number of times you want it to repeat itself and create numbers in the sequence Here's what I've come up with so far. Probably not the most elegant solution because of the nested function, but it does work! :) def morris(seed, limit): num = seed numberSet = [] def nextNum(num): num = list(str(num)) grouping = [] nextNum = [] for i in range(len(num)): try: if num[i] == num[i + 1]: grouping.append(num[i]) else: grouping.append(num[i]) nextNum.append(str(len(grouping)) + num[i]) grouping = [] except IndexError: grouping.append(num[i]) nextNum.append(str(len(grouping)) + num[i]) return ''.join(nextNum) for x in range(limit): numberSet.append(int(num)) num = nextNum(num) return numberSet -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
The generator in your original post /does/ rebind seed, but only on the
last iteration of the loop. You'll need to wrap that loop in another
loop if you want the generator to yield more than once.
As for communicating with a generator --- e.g. telling it to stop ---
this might be done by passing some kind of mutable argument to the
generator and then changing the value of that mutable object. However,
it's not a very elegant solution, and in this case there's not really
any reason to do it. Instead, if you want the generator to stop, just
stop asking it to yield:
for number in morris_sequence_generator(seed):
if it_is_time_to_stop():
break
And:
- No need to convert str(seed) to a list! Strings are indexable.
- Instead of using try...except IndexError to detect the end of the
loop, just change the loop to range(len(seed) - 1) and do the yield
after the loop finishes.
- Use xrange instead of range. range is evil.
Bonus points:
Write the generator to work on a seed which is an iterable of unknown
length.
Super bonus points:
Print the Nth element in the sequence without holding more than N
groups of {digit, number of occurences} of state information. You'll
need to do this if you want to get very far: According to Wikipedia,
the 70th term of the look-and-say sequence has 179,691,598 digits.
--
http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote: It is meant to take a number and generate the next number that follows according to the Morris sequence. It works for a single number, but what I'd like it to do is either: 1. repeat indefinitely and have the number of times controlled elsewhere in the program (e.g., use the morris() generator in a for loop and use that context to tell it when to stop) 2. just make it a function that takes a second argument, that being the number of times you want it to repeat itself and create numbers in the sequence Definitely go for (1). The Morris sequence is a great candidate to implement as a generator. As a generator, it will be more flexible and efficient than (2). def morris(num): Generate the Morris sequence starting at num. num = str(num) yield num while True: result, cur, run = [], None, 0 for digit in num+'\n': if digit == cur: run += 1 else: if cur is not None: result.append(str(run)) result.append(cur) cur, run = digit, 1 num = ''.join(result) yield num # Example usage: from itertools import islice for n in islice(morris(1), 10): print n # Output: 1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211 --Ben -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
Ben Cartwright wrote: Definitely go for (1). The Morris sequence is a great candidate to implement as a generator. As a generator, it will be more flexible and efficient than (2). Actually I was just thinking about this and it seems like, at least for my purpose (to simply return a list of numbers), I don't need a generator. My understanding of a generator is that you do something to each yielded value before returning to the generator (so that you might not return at all), but since I'm not handling the individual numbers, just getting a list, it seems I don't need them to be yielded. Of course, a generator would allow the process to be done over and over, I suppose, which is what I wanted, I just couldn't figure out how to keep using the new values. -- http://mail.python.org/mailman/listinfo/python-list
Re: how to make a generator use the last yielded value when it regains control
John Salerno wrote:
Actually I was just thinking about this and it seems like, at least for
my purpose (to simply return a list of numbers), I don't need a
generator.
Yes, if it's just a list of numbers you need, a generator is more
flexibility than you need. A generator would only come in handy if,
say, you wanted to give your users the option of getting the next N
items in the sequence, *without* having to recompute everything from
scratch.
My understanding of a generator is that you do something to
each yielded value before returning to the generator (so that you might
not return at all),
A generator is just an object that spits out values upon request; it
doesn't care what the caller does with those values.
There's many different ways to use generators; a few examples:
# Get a list of the first 10
from itertools import islice
m = [n for n in islice(morris(1), 10)]
# Prompt user between each iteration
for n in morris(1):
if raw_input('keep going? ') != 'y':
break
print n
# Alternate way of writing the above
g = morris(1)
while raw_input('keep going? ') == 'y':
print g.next()
--Ben
--
http://mail.python.org/mailman/listinfo/python-list
