Comprehension with two variables - explanation needed
Steven D'Aprano
steve at pearwood.info
Mon Nov 24 05:42:53 CET 2014
On Sun, 23 Nov 2014 08:45:39 -0800, Rustom Mody wrote:
> 2. "List comprehensions are syntactic sugar for for loops" Cannot
> technically quarrel with that as that is the position of the official
> docs.
> However to me it puts the cart before the horse. Its like saying that
>
> def foo(x): return x+1
>
> is just the same as
>
> 0 LOAD_FAST 0 (x)
> 3 LOAD_CONST 1 (1)
> 6 BINARY_ADD
> 7 RETURN_VALUE
>
>
> (output of dis)
The two situations are not related. The output of dis is an
implementation detail. Try running it under IronPython or Jython and see
what you get. Even in CPython, it is still an implementation detail
subject to change. Today dis() returns the above, tomorrow it may return:
0 LOAD_GLOBAL 0 (x)
3 INCREMENT
5 RETURN_VALUE
(say), and the Python code remains the same even though the byte code is
different.
Whereas the statement that "comprehensions are syntactic sugar for for-
loops" is a statement about the semantics of comprehensions. It's a
language promise, part of the API of Python, and not subject to change
without a period of deprecation. It is a promise that
[expression for name in sequence]
is closely equivalent to:
for name in sequence:
expression
(They are not *identical* because list comprehensions collect the result
of expression into a list, set comprehensions collect them into a set,
etc. But the actual looping part is the same.)
> 3. So how should one think of list comprehensions?
> As a python/executable version of 'set-builder notation'
> http://en.wikipedia.org/wiki/Set-builder_notation
For those who learned, and remember, set-builder notation, that is an
excellent analogy.
> 4. Finally to the OP (assuming you wanted a prime-number generator)
> Heres a solution for your consideration.
>
> First a one-line solution in haskell
>
> sieve (p:xs) = p:sieve [x | x <- xs, x `mod` p /= 0]
Don't use that! That is a horribly inefficient way to generate primes.
Mathematically, it is a version of Euler's Sieve. It is sometimes wrongly
described as "Sieve of Eratosthenes", but that is wrong. Due to it's
horrible performance, Melissa O'Neill calls this the "Sleight on
Eratosthenes":
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Asymptotic behaviour of this is O(N**2/(log N)**2) which is worse than
trial division and only *marginally* better than this stupidly naive
version:
def primes0():
i = 2
yield i
while True:
i += 1
composite = False
for p in range(2, i):
if i%p == 0:
composite = True
if not composite: # It must be a prime.
yield i
> Call with sieve [2..]
>
> Now a pythonification of that
[...]
--
Steven
More information about the Python-list
mailing list