Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Idea for key parameter in all() builting, would it be feasible? (http://www.velocityreviews.com/forums/t961932-idea-for-key-parameter-in-all-builting-would-it-be-feasible.html)

russ.pobox@gmail.com 06-19-2013 04:14 PM

Idea for key parameter in all() builting, would it be feasible?
 
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.

>>> all(xrange(10**9))


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.

>>> all(xrange(1, 10**9))


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

>>> all(map(lambda x: bool(x), xrange(10**9)))


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.

>>> all(xrange(10**9), key=lambda x: bool(x))


Which would return False instantly (ideally).

Chris Angelico 06-19-2013 04:20 PM

Re: Idea for key parameter in all() builting, would it be feasible?
 
On Thu, Jun 20, 2013 at 2:14 AM, <russ.pobox@gmail.com> wrote:
> 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.
>
>>>> all(map(lambda x: bool(x), xrange(10**9)))

>
> 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.
>
>>>> all(xrange(10**9), key=lambda x: bool(x))

>
> 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:

>>> from itertools import imap
>>> all(imap(lambda x: bool(x), xrange(10**9)))

False

It's roughly instant, like you would expect.

ChrisA

russ.pobox@gmail.com 06-19-2013 04:32 PM

Re: Idea for key parameter in all() builting, would it be feasible?
 
>All you need is the iterator version of map(). In Python 3, that's the
>normal map(); in Python 2, use this:


>>>> from itertools import imap
>>>> all(imap(lambda x: bool(x), xrange(10**9)))

>False


>It's roughly instant, like you would expect.


>ChrisA


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!

Russel Walker 06-20-2013 10:05 AM

Re: Idea for key parameter in all() builting, would it be feasible?
 
> If you're getting this via the mailing list, just hit Reply, and then
>
> change the To: address to python-list@python.org - 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

>>> all(map(lambda x: n%x, xrange(2, n)))


could be better written as

>>> all(n%x for n in xrange(2, n))


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:

>>> timer(primeset, 10**6)

1.0981476384030202

>>> # straight forward Eratosthenes sieve
>>> timer(primes, 10**6)

0.5887037628822327


Antoon Pardon 06-20-2013 10:45 AM

Re: Idea for key parameter in all() builting, would it be feasible?
 
Op 19-06-13 18:14, russ.pobox@gmail.com schreef:
>
>>>> all(map(lambda x: bool(x), xrange(10**9)))


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)))



Russel Walker 06-20-2013 02:49 PM

Re: Idea for key parameter in all() builting, would it be feasible?
 
On Thursday, June 20, 2013 12:45:27 PM UTC+2, Antoon Pardon wrote:
> Op 19-06-13 18:14, russ.pobox@gmail.com schreef:
>
> >

>
> >>>> all(map(lambda x: bool(x), xrange(10**9)))

>
>
>
> 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.

>>> all(map(lambda x: n%x, xrange(2, n)))


Chris Angelico 06-20-2013 03:48 PM

Re: Idea for key parameter in all() builting, would it be feasible?
 
On Fri, Jun 21, 2013 at 12:49 AM, Russel Walker <russ.pobox@gmail.com> wrote:
> On Thursday, June 20, 2013 12:45:27 PM UTC+2, Antoon Pardon wrote:
>> Op 19-06-13 18:14, russ.pobox@gmail.com schreef:
>>
>> >

>>
>> >>>> all(map(lambda x: bool(x), xrange(10**9)))

>>
>> 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.


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


All times are GMT. The time now is 08:06 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.