I tried to code the Sieve of Erastosthenes with generators:
def sieve_all(n = 100):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# filter out all multiples of p from stream
stream = (q for q in stream if q%p != 0)
# print primes up to 100
print list(sieve_all( 100))
but it didn't work. I had to replace
stream = (q for q in stream if q%p != 0)
with
def s1(p):
return (q for q in stream if q%p != 0)
stream = s1(p)
or alternatively
stream = (lambda p,stream: \
(q for q in stream if q%p != 0)) (p, stream)
I had thought that genexps worked like that automatically, i.e. the
stuff inside the genexp was in its own scope. If it's not real
obvious what's happening instead, that's a sign that the current
behavior is a wart. (The problem is that p in my first genexp comes
from the outer scope, and changes as the sieve iterates through the
stream)
Oh well. 7 1236
Paul Rubin wrote: I tried to code the Sieve of Erastosthenes with generators:
def sieve_all(n = 100): # yield all primes up to n stream = iter(xrange(2, n)) while True: p = stream.next() yield p # filter out all multiples of p from stream stream = (q for q in stream if q%p != 0)
# print primes up to 100 print list(sieve_all( 100))
but it didn't work. I had to replace
stream = (q for q in stream if q%p != 0)
with
def s1(p): return (q for q in stream if q%p != 0) stream = s1(p)
or alternatively
stream = (lambda p,stream: \ (q for q in stream if q%p != 0)) (p, stream)
You do realize that you're creating a new level of generator nesting
with each iteration of the while loop, right? You will quickly hit the
maximum recursion limit. Try generating the first 1000 primes.
I had thought that genexps worked like that automatically, i.e. the stuff inside the genexp was in its own scope. If it's not real obvious what's happening instead, that's a sign that the current behavior is a wart. (The problem is that p in my first genexp comes from the outer scope, and changes as the sieve iterates through the stream)
I don't see how it's a wart. p is accessed (i.e., not set) by the
genexp. Consistent with the function scoping rules in... http://www.python.org/doc/faq/progra...bles-in-python
....Python treats p in the genexp as a non-local variable.
--Ben
"Ben Cartwright" <be****@gmail.c om> writes: You do realize that you're creating a new level of generator nesting with each iteration of the while loop, right? You will quickly hit the maximum recursion limit. Try generating the first 1000 primes.
Yes, I know about the generator nesting, that was the point. The
Sieve of Eraswhatsisname takes linear space by definition. It's
usually done with an array but this version uses nested generators
instead. I didn't bother to test whether they counted against the
recursion limit, so it's informative to know that they do.
I don't see how it's a wart. p is accessed (i.e., not set) by the genexp. Consistent with the function scoping rules in... http://www.python.org/doc/faq/progra...bles-in-python ...Python treats p in the genexp as a non-local variable.
Yeah, it's just counterintuitiv e is all. I guess the natural way to
express this would have been with tail recursion instead of a while
loop.
The generator is in its own scope. For proof, try accessing q outside
the generator.
There are two possibilities. The first is that you don't know what
closures are and are complaining that python has them. That would be
amusingly ironic, but I'm guessing you do know (if you don't, google
"make_adder " and be enlightened)
The second is that you don't like the late-binding behavior of
generator expressions. PEP 289 has this to say: After much discussion, it was decided that the first (outermost) for-expression should be evaluated immediately and that the remaining expressions be evaluated when the generator is executed.
and:
After exploring many possibilities, a consensus emerged that [...] [for] more complex applications, full generator definitions are always superior in terms of being obvious about scope, lifetime, and binding
And as an illustration of that last point, consider:
def sieve_all(n = 100):
# generate all primes up to n
def filter_multiple s(input, m):
for q in input:
if q % m != 0:
yield q
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
# this is now a redundant comment.
# filter out all multiples of p from stream
stream = filter_multiple s(stream, p)
p
Paul Rubin <http://ph****@NOSPAM.i nvalid> writes: Yeah, it's just counterintuitiv e is all. I guess the natural way to express this would have been with tail recursion instead of a while loop.
FWIW, here's a listcomp version:
def s2(n=100):
stream = range(2,n)
while stream:
p = stream[0]
yield p
stream = [s for s in stream if s%p != 0]
print list(s2(100))
This should have the same space consumption and approx. running time
as the classic sieve. The genexp version actually used O(n/log(n))
space instead of linear space, I think.
Paul Rubin wrote: I tried to code the Sieve of Erastosthenes with generators:
def sieve_all(n = 100): # yield all primes up to n stream = iter(xrange(2, n)) while True: p = stream.next() yield p # filter out all multiples of p from stream stream = (q for q in stream if q%p != 0)
# print primes up to 100 print list(sieve_all( 100))
but it didn't work.
This is a known issue with the scope rules in loops which has bitten
many (including
myself; there is a long thread involving me and Jacek Generowitz
debating this at
death, you may find it if you google the newsgroup).
I would be curious to know if your code would work the way you expect
in Haskell
(I know it would for 'for' loop, dunno about 'while' loops, I am
completely ignorant
in Haskell).
Michele Simionato
"Paul Du Bois" <pa*********@gm ail.com> writes: The second is that you don't like the late-binding behavior of generator expressions. PEP 289 has this to say:
After much discussion, it was decided that the first (outermost) for-expression should be evaluated immediately and that the remaining expressions be evaluated when the generator is executed.
Thanks. That PEP is informative. It shows that I stumbled into
something that other people found confusing too, and that alternatives
were considered that turned out not to be better.
Paul Rubin wrote: "Paul Du Bois" <pa*********@gm ail.com> writes: The second is that you don't like the late-binding behavior of generator expressions. PEP 289 has this to say:
After much discussion, it was decided that the first (outermost) for-expression should be evaluated immediately and that the remaining expressions be evaluated when the generator is executed.
Thanks. That PEP is informative. It shows that I stumbled into something that other people found confusing too, and that alternatives were considered that turned out not to be better.
The net effect of the bad version seems to be that you're
not getting a new generator from
stream = (q for q in stream if q%p != 0)
(* disassembly shown below.)
Disassembly seems to show the program getting a pre-compiled
generator expression code block, and binding the new value
of p to it, then getting iter(stream), which is stream. As
Paul Du Bois says, the outer loop is fixed, but the
subsequent if-expression is liable to change.
So 3 passes because 3%2 != 0
4 passes because 4%3 != 0
5 passes because 5%4 != 0
and so on.
Interesting.
* Disassembly of stream = ...:
6 47 LOAD_CLOSURE 0 (p)
50 LOAD_CONST 2 (<code object
<generator expression> at 009D65E0, file "try_eratos.py" ,
line 6>)
53 MAKE_CLOSURE 0
56 LOAD_FAST 1 (stream)
59 GET_ITER
60 CALL_FUNCTION 1
63 STORE_FAST 1 (stream) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: rw |
last post by:
In php 5.0.3 i found that
$s="a";
if(isset($s->prop))
echo "surprise";
In previous php it was false;
Is it bug?
--
Rob Was
|
by: Bryan |
last post by:
i thought that LC and genexp were supposed to be faster than map. i also thought i read somewhere in this group that
the slowest looping mechanism in 2.4 is 20% faster than the fastest looping mechanism in 2.3. if i'm wrong about this,
remembered wrong or did something wrong, please let me know. here are some timeit tests i did on my machine....
|
by: Bengt Richter |
last post by:
E.g., so we could write
for x in seq if x is not None:
print repr(x), "isn't None ;-)"
instead of
for x in (x for x in seq if x is not None):
print repr(x), "isn't None ;-)"
|
by: Boris Borcic |
last post by:
On the python3000 mailing list there was some discussion of a "comprehension
syntax" for reduce.
This inspired me the following proof-of-concept in pure python 2.5a1, although I
don't know if it relies on an intended feature or a(n unintended) bug.
Cheers, BB
--
def ireduce(gen) :
|
by: Rakesh Parekh |
last post by:
To my great surprise the following code is not working. I expect
TextBox1.Text to be
changed each time the dropdownlist selected index changes. It works in
Windows application but
surprisingly not not WebApplication web form.
Private Sub Page_Load(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles MyBase.Load...
| |
by: Sathyaish |
last post by:
I am expecting a VBA code module in one of the VBA apps, but much to my
astonishment, I don't seem to find my way through it. It seems like I
am looking at a fully compiled binary.
I have an MDB (Microsoft Access 2000) file that I am guessing is a
compiled binary written in Visual Basic for Applications (VBA).
I've done a fairly decent...
|
by: Giovanni Bajo |
last post by:
Hello,
I found this strange:
python -mtimeit "sum(int(L) for L in xrange(3000))"
100 loops, best of 3: 5.04 msec per loop
python -mtimeit "import itertools; sum(itertools.imap(int, xrange(3000)))"
100 loops, best of 3: 3.6 msec per loop
|
by: codefire |
last post by:
I thought the 'is' operator was used to identify identical objects,
whereas the '==' operator checked equality. Well, I got a surprise
here:
IDLE 1.1.3
True
True
True
True
|
by: Paul Rubin |
last post by:
I have a doc with a bunch of fields like:
<foo bar="spam">stuff</foo>
<foo bar="penguin">other stuff</foo>
and sometimes
<foo bar="parrot"></foo>
I use ElementTree to parse the doc and I use the .text attribute
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |