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

Discussion in 'Python' started by russ.pobox@gmail.com, Jun 19, 2013.

  1. Guest

    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).
    , Jun 19, 2013
    #1
    1. Advertising

  2. On Thu, Jun 20, 2013 at 2:14 AM, <> 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
    Chris Angelico, Jun 19, 2013
    #2
    1. Advertising

  3. Guest

    >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!
    , Jun 19, 2013
    #3
  4. > If you're getting this via the mailing list, just hit Reply, and then
    >
    > change the To: address to - 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
    Russel Walker, Jun 20, 2013
    #4
  5. Op 19-06-13 18:14, 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)))
    Antoon Pardon, Jun 20, 2013
    #5
  6. On Thursday, June 20, 2013 12:45:27 PM UTC+2, Antoon Pardon wrote:
    > Op 19-06-13 18:14, 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)))
    Russel Walker, Jun 20, 2013
    #6
  7. On Fri, Jun 21, 2013 at 12:49 AM, Russel Walker <> wrote:
    > On Thursday, June 20, 2013 12:45:27 PM UTC+2, Antoon Pardon wrote:
    >> Op 19-06-13 18:14, 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
    Chris Angelico, Jun 20, 2013
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. HUANG Huan
    Replies:
    2
    Views:
    664
    Dave Higton
    Feb 24, 2004
  2. lapenta[
    Replies:
    1
    Views:
    743
    Mike Treseler
    Nov 6, 2004
  3. Taras_96
    Replies:
    2
    Views:
    4,858
    Taras_96
    Aug 3, 2005
  4. Newbie
    Replies:
    4
    Views:
    388
    Newbie
    Oct 27, 2003
  5. Shepard Tate

    Is this feasible?

    Shepard Tate, Feb 25, 2004, in forum: HTML
    Replies:
    25
    Views:
    840
    Whitecrest
    Mar 1, 2004
Loading...

Share This Page