Re: [Tutor] Workaround for limitation in xrange()?

[Kent Johnson]

Alan Gauld wrote:
> "Dick Moores" <[EMAIL PROTECTED]> wrote in message 
> news:[EMAIL PROTECTED]
>> Encapsulate the while loop in a generator:
>> def count(limit):
>>   n=0
>>   while n> yield n
>> n += 1
>>
>> All 3 are essentially the same, aren't they. Which makes me feel 
>> even
>> dumber, because I don't understand any of them. I've consulted 3
>> books, and still don't understand the use of yield.
> 
> Think of yield as being the same as return except that next time
> you "call the function" all the state is preserved and it picks up 
> processing
> after the yield.

A small correction - in normal use you only call the generator function 
once. The value it returns is a generator, an object with a next() 
method. It is the next() method that is called repeatedly to re-enter 
the function and return the next value. When there are no more values to 
return, the next() method raises StopIteration.

For example:
In [1]: def f(): yield 1
...:

In [2]: f
Out[2]: 

f is a generator function. The result of calling it is a generator:
In [3]: p=f()

In [4]: p
Out[4]: 

The generator p is not callable:
In [5]: p()
---
 Traceback (most recent call last)

D:\Projects\e3po\ in ()

: 'generator' object is not callable

p.next() yields values, then raises StopIteration:
In [6]: p.next()
Out[6]: 1

In [7]: p.next()
---
 Traceback (most recent call last)

D:\Projects\e3po\ in ()

:

The generator also has an __iter__() method that returns the generator 
itself:

In [9]: p.__iter__() is p
Out[9]: True

In other words, a generator satisfies the iterator protocol
http://docs.python.org/lib/typeiter.html
and it can be used any where an iterator can be used, such as in a for 
statement.

Kent

> 
> So first time you call count above it returns 0
> next time you call it it executes the n+= 1 and goes round the loop
> again until it hits yield when it returns 1.
> next time you call it executes y+=1 again, but because the state has
> been remembered n goes to 2 and yield returns that
> and so on until you reach n = limit at which point it just
> exits with StopIteration.  Here is a short example:
> 
 def y(n):
> ...   j = 0
> ...   while j < n:
> ... yield j
> ... j += 1
> ...
 try:
> ...x = y(7)
> ...for n in range(20):
> ...  print x.next()
> ... except StopIteration:
> ...   print 'Reached the end'
> ...
> 0
> 1
> 2
> 3
> 4
> 5
> 6
> Reached the end
> 
> Does that help?
> 
> 


___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Alan Gauld]

"Dick Moores" <[EMAIL PROTECTED]> wrote in message 
news:[EMAIL PROTECTED]
> Encapsulate the while loop in a generator:
> def count(limit):
>   n=0
>   while n yield n
> n += 1
>
> All 3 are essentially the same, aren't they. Which makes me feel 
> even
> dumber, because I don't understand any of them. I've consulted 3
> books, and still don't understand the use of yield.

Think of yield as being the same as return except that next time
you "call the function" all the state is preserved and it picks up 
processing
after the yield.

So first time you call count above it returns 0
next time you call it it executes the n+= 1 and goes round the loop
again until it hits yield when it returns 1.
next time you call it executes y+=1 again, but because the state has
been remembered n goes to 2 and yield returns that
and so on until you reach n = limit at which point it just
exits with StopIteration.  Here is a short example:

>>> def y(n):
...   j = 0
...   while j < n:
... yield j
... j += 1
...
>>> try:
...x = y(7)
...for n in range(20):
...  print x.next()
... except StopIteration:
...   print 'Reached the end'
...
0
1
2
3
4
5
6
Reached the end
>>>

Does that help?


-- 
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld 


___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Dick Moores]

At 12:31 PM 10/10/2006, Marc Poulin wrote:

>--- Dick Moores <[EMAIL PROTECTED]> wrote:
> >
> > Andrei's
> > Write your own iterator:
> >  >>> def hugerange(minval, maxval):
> > ... val = minval
> > ... while val < maxval:
> > ... yield val
> > ... val += 1
> >
> > All 3 are essentially the same, aren't they. Which
> > makes me feel even
> > dumber, because I don't understand any of them. I've
> > consulted 3
> > books, and still don't understand the use of yield.
> >
>
>This is an example of a "coroutine".
>See http://en.wikipedia.org/wiki/Coroutine
>
>def hugerange(minval, maxval):
> val = minval
> while val < maxval:
> yield val
> ### return value of "val" to calling routine
> ### at this point and place
> ### hugerange() function temporarily
> ### on hold ...
> ###
> ### next call to hugerange()
> ### resumes at this point with
> ### all previous variable values
> ### still intact ...
> val += 1

Ah, it's beginning to make sense. However, it seems there's a need to 
do this because the while loop is inside a function (made generator). 
The while loop of mine in 
 is not in a 
function, so it seems I don't need a generator. Am I correct? I have 
a real interest in speed, however, and being forced to use the while 
loop for k larger than 2**31-1 really slows things down. It seems a 
while loop is about 20% slower than an equivalent for loop. Would 
using a generator be a help speedwise? I suspect it wouldn't. How about it?

Thanks very much, Marc.

Dick



___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Kent Johnson]

Dick Moores wrote:
> At 11:34 AM 10/10/2006, Kent Johnson wrote:
>> Dick Moores wrote:
>>> Here are the suggestions I've received:
>> 
>>
>>> All 3 are essentially the same, aren't they. 
>>> Which makes me feel even dumber, because I 
>>> don't understand any of them. I've consulted 3 
>>> books, and still don't understand the use of yield.
>> Yes, they are pretty much the same. Mine is 
>> bare-bones, just doing what you specifically 
>> asked for. Danny's is a full replacement for xrange(); Andrei's is in 
>> between.
>>
>> Here is a good introduction to generators:
>> http://www.python.org/doc/2.2.3/whatsnew/node5.html
> 
> While I'm studying that, could you modify my 
> while loop so that it incorporates your 
> suggestion in a way that improves it? That would 
> be a big help to me in understanding generators 
> and the use of yield, I believe.

I'm not certain I would call it an improvement, but it would look just 
like your loop with xrange(). If the generator function is called 
count(), your loop would be
for i in count(2**100):  # ;)
   # process i

The big advantage of generators is they let you encapsulate the logic 
that generates a sequence. This makes it easy to reuse a sequence 
without having to duplicate the sequence generation logic in multiple 
loops. Sometimes this can make your loop clearer because it can focus on 
processing the sequence rather than generating it. Sometimes it can 
greatly simplify your logic. This happens when both the generation of a 
sequence and the processing of it involve maintaining state.

Here's a very artificial and possibly helpful example. Consider the sequence
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...

Imagine you want to do something with every third element of that 
sequence, for example sum them. Maybe it's not so hard to do this in a 
simple loop but my head starts to hurt thinking about it.

OK, so let's encapsulate the sequence into a generator:
In [13]: def multicount(limit):
: for i in range(1, limit+1):
: for j in range(1, i+1):
: yield j
:
:

In [14]: list(multicount(5))
Out[14]: [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]

Now summing every third element is easy:
In [16]: sum(list(multicount(5))[::3])
Out[16]: 10

Does that help?

Kent

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Dick Moores]

At 11:34 AM 10/10/2006, Kent Johnson wrote:
>Dick Moores wrote:
>>Here are the suggestions I've received:
>
>
>>All 3 are essentially the same, aren't they. 
>>Which makes me feel even dumber, because I 
>>don't understand any of them. I've consulted 3 
>>books, and still don't understand the use of yield.
>
>Yes, they are pretty much the same. Mine is 
>bare-bones, just doing what you specifically 
>asked for. Danny's is a full replacement for xrange(); Andrei's is in between.
>
>Here is a good introduction to generators:
>http://www.python.org/doc/2.2.3/whatsnew/node5.html

While I'm studying that, could you modify my 
while loop so that it incorporates your 
suggestion in a way that improves it? That would 
be a big help to me in understanding generators 
and the use of yield, I believe.

I don't want to give up on generators, even 
though your referenced article grants me 
permission to do so: "Generators are considered a 
new part of the core Python language, but 
learning or using them isn't compulsory; if they 
don't solve any problems that you have, feel free to ignore them."

>>I've realized now that all 3 scripts require an 
>>immense number of calls to random()
>
>Um, yeah, more than 2**31-1, right? :-)

At least several trillions, I'm thinking now, naively.

>By the way your approach to testing the 
>'goodness' of random() is pretty naive. For 
>example a random() that just repeats 0...99 over 
>and over would score very well. For large repeat 
>counts it could even repeat the same number for 
>a while and score well: 1 etc.

Sure, but passing the 3 tests I had in mind would 
be necessary if not sufficient conditions. 
Obviously random() would not be of the sorts you 
mention. Functions like those wouldn't be chosen for use in Python, right?

>  You might be interested in this article and the links at the bottom:
>http://en.wikipedia.org/wiki/Pseudo-random_number_generator

I'll be sure to check this out. And a friend 
tells me he has the Knuth vol. 2 (with that 
"Chapter 3, pp.1–193. Extensive coverage of 
statistical tests for non-randomness).

Dick



___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Marc Poulin]

--- Dick Moores <[EMAIL PROTECTED]> wrote:
> 
> Andrei's
> Write your own iterator:
>  >>> def hugerange(minval, maxval):
> ... val = minval
> ... while val < maxval:
> ... yield val
> ... val += 1
> 
> All 3 are essentially the same, aren't they. Which
> makes me feel even 
> dumber, because I don't understand any of them. I've
> consulted 3 
> books, and still don't understand the use of yield.
> 

This is an example of a "coroutine".
See http://en.wikipedia.org/wiki/Coroutine

def hugerange(minval, maxval):
val = minval
while val < maxval:
yield val
### return value of "val" to calling routine
### at this point and place
### hugerange() function temporarily
### on hold ...
###
### next call to hugerange()
### resumes at this point with
### all previous variable values
### still intact ...
val += 1


__
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Kent Johnson]

Dick Moores wrote:
> Here are the suggestions I've received:


> 
> All 3 are essentially the same, aren't they. Which makes me feel even 
> dumber, because I don't understand any of them. I've consulted 3 
> books, and still don't understand the use of yield.

Yes, they are pretty much the same. Mine is bare-bones, just doing what 
you specifically asked for. Danny's is a full replacement for xrange(); 
Andrei's is in between.

Here is a good introduction to generators:
http://www.python.org/doc/2.2.3/whatsnew/node5.html

> I've realized now that all 3 scripts require an immense number of 
> calls to random()

Um, yeah, more than 2**31-1, right? :-)

By the way your approach to testing the 'goodness' of random() is pretty 
naive. For example a random() that just repeats 0...99 over and over 
would score very well. For large repeat counts it could even repeat the 
same number for a while and score well: 1 etc. 
You might be interested in this article and the links at the bottom:
http://en.wikipedia.org/wiki/Pseudo-random_number_generator

Kent

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Dick Moores]

>
>> >>> for x in xrange(2**31):
>> pass
>>
>>Traceback (most recent call last):
>>   File "", line 1, in 
>> for x in xrange(2**31):
>>OverflowError: long int too large to convert to int
>

Here are the suggestions I've received:

Danny's
>#
>def myxrange(m, n=None, skip=1):
> """An xrange-like function that can deal with long ints.
> Note: doesn't deal with negative ranges particularly well."""
> if n is None:
>m, n = 0, m
> i = m
> while i < n:
> yield i
> i = i + skip
>#

Kent's
Encapsulate the while loop in a generator:
def count(limit):
   n=0
   while n>> def hugerange(minval, maxval):
... val = minval
... while val < maxval:
... yield val
... val += 1

All 3 are essentially the same, aren't they. Which makes me feel even 
dumber, because I don't understand any of them. I've consulted 3 
books, and still don't understand the use of yield.

Let me show you what I was doing when I ran into the 2**31-1 
limitation: 

This is one of my attempts to test the degree of uniformity of 
random(). The others are seeing how close the average random() return 
comes to 0.5, and using random() in an approximation of pi.

I've realized now that all 3 scripts require an immense number of 
calls to random(), so many that I wouldn't be able to use my computer 
for anything else for weeks, maybe months. But be that as it may, I'd 
still like to know how to use yield in my 1histogram-5a.

For your convenience, here's the list h, and the while loop I used:

h = 100*[0]

c = 0
while c < k:
 r = random()
 i = int(math.floor(100*r))
 h[i] += 1
 c += 1

So, for a random() return of 0.27862506717494118, i would be 27, and 
h[27] would be incremented by 1.
Thanks,

Dick


___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Danny Yoo]

> >>> for x in xrange(2**31):
> pass
>
> Traceback (most recent call last):
>   File "", line 1, in 
> for x in xrange(2**31):
> OverflowError: long int too large to convert to int


Hi Dick,

Hmmm... I'd consider this a misfeature in the implementation.  Apparently 
xrange (and range) must be built with regular ints, not long ints.  This 
limitation is documented, although I think this is inconsistent and a bad 
thing.

 http://www.python.org/doc/2.3.5/lib/built-in-funcs.html#l2h-73
 http://www.python.org/doc/2.3.5/lib/built-in-funcs.html#l2h-55


In the meantime, you can build your own version of xrange that should work 
on long ints.  Here is an example:

#
def myxrange(m, n=None, skip=1):
 """An xrange-like function that can deal with long ints.
 Note: doesn't deal with negative ranges particularly well."""
 if n is None:
m, n = 0, m
 i = m
 while i < n:
 yield i
 i = i + skip
#


This is a "generator" that does pretty much what you'll want.

##
>>> list(myxrange(1, 5))
[1, 2, 3, 4]
>>> list(myxrange(2**32, 2**32 + 5))
[4294967296L, 4294967297L, 4294967298L, 4294967299L, 4294967300L]
##


Note: this is a quick-and-dirty function; I wouldn't use it in production 
yet.  It needs some more work to reject bad input.  If you want, we can 
talk about exhaustively testing the function using robust equivalence 
class testing.  *grin*


Best of wishes!
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Andrei]

Dick Moores  rcblue.com> writes:

 
> I can think of 2 workarounds for this 2**31 limitation in xrange(). 
> Use a while loop instead. Or use 2 or more for loops, keeping the 
> number of cycles in each under 2**31.
> 
> Are there others?

Write your own iterator:

>>> def hugerange(minval, maxval):
... val = minval
... while val < maxval:
... yield val
... val += 1
...
>>> for i in hugerange(2**31, 2**31 + 2):
... print i
...
2147483648
2147483649

It might be slower than Python's xrange implementation (haven't tested), but it
will take anything you throw at it as long as Python itself can handle it.

Yours,

Andrei

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Workaround for limitation in xrange()?

[Kent Johnson]

Dick Moores wrote:
>  >>> for x in xrange(2**31):
>  pass
> 
> Traceback (most recent call last):
>File "", line 1, in 
>  for x in xrange(2**31):
> OverflowError: long int too large to convert to int
>  >>>
> 
> I can think of 2 workarounds for this 2**31 limitation in xrange(). 
> Use a while loop instead. Or use 2 or more for loops, keeping the 
> number of cycles in each under 2**31.
> 
> Are there others?

Encapsulate the while loop in a generator:
def count(limit):
   n=0
   while nhttp://mail.python.org/mailman/listinfo/tutor

[Tutor] Workaround for limitation in xrange()?

[Dick Moores]

 >>> for x in xrange(2**31):
 pass

Traceback (most recent call last):
   File "", line 1, in 
 for x in xrange(2**31):
OverflowError: long int too large to convert to int
 >>>

I can think of 2 workarounds for this 2**31 limitation in xrange(). 
Use a while loop instead. Or use 2 or more for loops, keeping the 
number of cycles in each under 2**31.

Are there others?

Thanks,

Dick Moores

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor