Generators/iterators, Pythonicity, and primes
John Posner
jjposner at snet.net
Sun Apr 5 17:14:09 CEST 2009
Kay Schluehr said:
> g = (lambda primes = []:
> (n for n in count(2) \
> if
> (lambda n, primes: (n in primes if primes and
n<=primes[-1] \
> else
> (primes.append(n) or True \
> if all(n%p for p in primes if p <= sqrt(n)) \
> else False)))(n, primes)))()
Um ... did you say "easy"? :-) This is prodigious, and it's definitely a
solution to the generator-expression-only challenge I laid down. But I
think this is a case in which using a generator expression causes a loss
in "Pythonicity", rather than a gain. Many, many thanks for this!
Steven D'Aprano said:
> In other words, this is a crappy way to generate primes. It's a trick,
> not a good algorithm: slow and inefficient, as well as obfuscated.
I wasn't thinking at all about efficiency, so I'm not surprised that my
implementation -- a pretty simple adaptation of
http://code.activestate.com/recipes/576640 -- scores low in that
dimension. I was mainly looking for Pythonicity. I'm sure this means
different things to different people, PEP 20 notwithstanding. To me,
this is an important aspect of Pythonicity:
The final Python code looks like your initial back-of-the-napkin pseudo
code.
In the old days, that meant using filter(), because this function
mirrors the "sieve" concept in the Sieve of Eratosthenes. These days, I
believe that this condition:
if all(n%p for p in primes if p < sqrt(n)):
... closely resembles this pseudo code:
if the number cannot be evenly divided by all the primes we've
generated so far (and we can stop testing at the square root)
So I believe this algorithm is the *opposite* of obfuscated. It's
crystal clear (albeit a slowpoke).
Miles (and others) said:
> P.S. Gmail shows all your messages with a blank body and a text
> attachment containing your message; this is perhaps because your
> mailer includes an invalid blank Content-disposition header.
It might be my ISP (AT&T Yahoo), or it might be MS-Outlook. I'm sending
this message using Thunderbird 2.0.0.21. Any better?
-John
More information about the Python-list
mailing list