Idea for key parameter in all() builting, would it be feasible?

R

russ.pobox

I was mucking around, trying to code a prime sieve in one line. I don't know about filters and bit shifting and stuff like that but I thought I could do it with builtins, albeit a very long one line. This is the part of my stupid trick in question that got me wondering about a key parameter for all() and the "why" is below that.

[n for n in xrange(3, int(pow(upper, 0.5) + 1), 2)
if all(map(lambda d: n%d!=0, xrange(2, int(pow(n, 0.5) + 1))))]

Where upper is the upper bound for the sieve. That list comprehension will provide a list of prime numbers up to the square root of upper using trial division. Then that list was going to be used for the rest of the sieve using the set.difference method to remove multiples of all those primes.

That's when I realized that all() doesn't necessarily go through every itemin the alterable. It's stops the moment it finds a false value. You can test that that's true with.

It's instant because 0 is the false value and so it stops and returns falseafter only checking the first value. Also because we're using xrange the generator function cousin of range.

The following on the other hand should take a while.

And the following, although the same thing really as all(xrange(10**9)), isnot as instant and will take even longer than the above.

However if all by some chance (I don't know how this stuff works underneath) has a key parameter then we could do something like.

Which would return False instantly (ideally).
 
C

Chris Angelico

And the following, although the same thing really as all(xrange(10**9)), is not as instant and will take even longer than the above.


However if all by some chance (I don't know how this stuff works underneath) has a key parameter then we could do something like.


Which would return False instantly (ideally).

All you need is the iterator version of map(). In Python 3, that's the
normal map(); in Python 2, use this:
False

It's roughly instant, like you would expect.

ChrisA
 
R

russ.pobox

All you need is the iterator version of map(). In Python 3, that's the
normal map(); in Python 2, use this:

It's roughly instant, like you would expect.

This probably isn't the way to post a reply on your own thread (I added an angle bracket to every line above :p) but last time clicked reply to author not knowing that is email. Anyways...

Thanks, I like itertools but had no idea imap. Although I did suspect Python3 would have something to say about this just to make me envious :D

It works like a charm!
 
R

Russel Walker

If you're getting this via the mailing list, just hit Reply, and then
change the To: address to (e-mail address removed) - that's the simplest

(assuming you don't have a Reply To List feature, but you wouldn't be

saying the above if you had one). That way, you get a citation line,

quoted text is marked, and it's taken a minimum of effort.

I guess it was pretty late last night but I didn't notice the huge post reply button *palmface*.
Awesome! Hey, if you *can* switch to Py3, do try to. It has heaps of

improvements, and it has a future. :)



ChrisA

Also I realized that aside from using map or the better alternative imap, an even better way to go might be a generator expression. Completely forgot about those.

So with a slightly less trivial example than the first

could be better written as

which is roughly 10 times faster and memory efficient, plus syntax is cleaner.
And roughly 1.5 times faster than imap which isn't much but prevents having to import itertools.

But I discovered a new itertools tool and my sieve was successful.

def primeset(upper):
return set([2]+range(3,upper,2)).difference(set.union(*[set(xrange(p+p,upper,p)) for p in [n for n in xrange(3,int(pow(upper, 0.5)+1)) if all(n%x for x in xrange(2, int(pow(n, 0.5)+1)))]]))

Here is the more sane version of the one-liner above.

def primeset(upper):
def isprime(n):
# brute force trial division
for d in xrange(2, int(pow(n, 0.5)+1)):
if n%d == 0: return False
return True
# Initial set of only odd numbers except for 2
numbers = set([2]+range(3, upper, 2))
# List of prime numbers up to square root of upper using brute force.
primes = [n for n in xrange(2, int(pow(upper,0.5)+1)) if isprime(n)]
# Multiples of all the prime numbers in the list above.
all_multiples = (set(xrange(p+p,upper,p)) for p in primes)
# This was allot faster than reduce(set.union, all_multiples)
multiples = set.union(*all_multiples)
# And the sieving action.
return numbers.difference(multiples)


Rough benchmarks:
1.0981476384030202
0.5887037628822327
 
A

Antoon Pardon

Op 19-06-13 18:14, (e-mail address removed) schreef:
Since you already have your answer, I just like to get your attention
to the fact the the lambda is superfluous here. Your expression
above is equivallent to

all(map(bool, xrange(10**9)))
 
R

Russel Walker

Op 19-06-13 18:14, (e-mail address removed) schreef:




Since you already have your answer, I just like to get your attention

to the fact the the lambda is superfluous here. Your expression

above is equivallent to



all(map(bool, xrange(10**9)))

That's true, I didn't notice that. Although it was a trivial example I was setting up from the actual code and couldn't think of what to shove inside lambda so bool got the short straw.

The latest example I showed was actually.
 
C

Chris Angelico

That's true, I didn't notice that. Although it was a trivial example I was setting up from the actual code and couldn't think of what to shove inside lambda so bool got the short straw.

Yeah, I've been guilty of that fairly often - making a trivial example
that can be trivialized even more. Sometimes all you need to do is
acknowledge it with a comment and move on, other times the additional
trivialization is a clue to the actual problem :)

In this particular case, all() will boolify anyway, so you don't even
need map. But that would completely destroy your example:

all(xrange(10**9)) # Doesn't help with figuring out the original issue!

ChrisA
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top