Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #48722 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  Idea for key parameter in all() builting, would it be feasible? russ.pobox@gmail.com - 2013-06-19 09:14 -0700
    Re: Idea for key parameter in all() builting, would it be feasible? Chris Angelico <rosuav@gmail.com> - 2013-06-20 02:20 +1000
    Re: Idea for key parameter in all() builting, would it be feasible? russ.pobox@gmail.com - 2013-06-19 09:32 -0700
      Re: Idea for key parameter in all() builting, would it be feasible? Chris Angelico <rosuav@gmail.com> - 2013-06-20 02:39 +1000
        Re: Idea for key parameter in all() builting, would it be feasible? Russel Walker <russ.pobox@gmail.com> - 2013-06-20 03:05 -0700
    Re: Idea for key parameter in all() builting, would it be feasible? Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-06-20 12:45 +0200
      Re: Idea for key parameter in all() builting, would it be feasible? Russel Walker <russ.pobox@gmail.com> - 2013-06-20 07:49 -0700
        Re: Idea for key parameter in all() builting, would it be feasible? Chris Angelico <rosuav@gmail.com> - 2013-06-21 01:48 +1000

#48722 — 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 item in 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 false after 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)), 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).

[toc] | [next] | [standalone]

#48724

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

[toc] | [prev] | [next] | [standalone]

#48725

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

[toc] | [prev] | [next] | [standalone]

#48727

On Thu, Jun 20, 2013 at 2:32 AM,  <russ.pobox@gmail.com> wrote:
>>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...

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.

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

Awesome! Hey, if you *can* switch to Py3, do try to. It has heaps of
improvements, and it has a future. :)

ChrisA

[toc] | [prev] | [next] | [standalone]

#48783

> 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

[toc] | [prev] | [next] | [standalone]

#48784

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

[toc] | [prev] | [next] | [standalone]

#48797

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

[toc] | [prev] | [next] | [standalone]

#48803

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web