Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Unable to Understand grep and hash use for prime no.

by shankonit (Acolyte)
on Aug 04, 2015 at 03:03 UTC ( #1137324=perlquestion: print w/replies, xml ) Need Help??

shankonit has asked for the wisdom of the Perl Monks concerning the following question:

I'm unable to understand what exactly this code doing: exists $is_prime{$_} and $is_prime{$_}

my %is_prime; @primes = grep { ( exists $is_prime{$_} and $is_prime{$_} ) or ( $is_prime{$_} = is_prime($_) ) } @numbers;

I appreciate your time to read and answer and thank u in advance. :)

Replies are listed 'Best First'.
Re: Unable to Understand grep and hash use for prime no.
by 1nickt (Abbot) on Aug 04, 2015 at 05:01 UTC

    From the documentation on Perl grep():

    Evaluates the BLOCK or EXPR for each element of LIST (locally setting $_ to each element) and returns the list value con +sisting of those elements for which the expression evaluated to tr +ue. In scalar context, returns the number of times the expression + was true.

    So you are making a new list, @primes, from the original list, @numbers, including only those elements of @numbers for which the expression returns true.

    Your expression,

    { ( exists $is_prime{$_} and $is_prime{$_} ) or ( $is_prime{$_} = is_prime($_) ) }

    has two conditions. If either of those returns true for the number from @numbers currently being evaluated, the number is added to @primes.

    As grep goes through @numbers, it assigns each one to $_ as it is working with it.

    The first condition tests to see whether there is already an entry in the hash %is_prime for the current number:

    exists $is_prime{$_}

    If there is not, the second part of the first condition, after the and, is ignored and grep() goes on to the second condition. If the number does exist as a key in the hash,

    and $is_prime{$_}

    checks to see whether additionally the value in the hash is true (ie not 0 or undef).

    If that first condition returns true, the second condition is ignored. If the first condition is false, the second condition calls the sub is_prime() with the number:

    is_prime($_)

    . . . and if the sub returns true, the second condition both adds the number to the hash:

    $is_prime{$_} = # the assigned value is the result of is_prime($_) if that function re +turned true

    . . . and causes the expression to return true, which adds the number to @primes.

    Hope this helps.

    The way forward always starts with a minimal test.

      I was problem to know the correct flow of program. It's clear. Thanks.

Re: Unable to Understand grep and hash use for prime no.
by 1nickt (Abbot) on Aug 04, 2015 at 06:16 UTC

    Also, this might help you understand what is going on with

    exists $is_prime{$_} and $is_prime{$_}

    Run the code to see the differences between exists(), defined and true. See if you can understand the warnings this code gives.

    #!/usr/bin/perl use strict; use warnings; use feature qw/ say /; use Data::Dumper; $Data::Dumper::Sortkeys = 1; my %hash; $hash{'A'} = 1; $hash{'B'} = 0; $hash{'C'} = -1; $hash{'D'} = undef; say Data::Dumper->Dump([\%hash], ['*hash']); for (qw/ A B C D E /) { say "Key: $_ Val: $hash{$_}"; say exists $hash{$_} ? ' exists' : ' does not exist'; say defined $hash{$_} ? ' defined' : ' not defined'; say $hash{$_} ? ' true' : ' false'; say '- -' x 20; } __END__
    The way forward always starts with a minimal test.
Re: Unable to Understand grep and hash use for prime no.
by GrandFather (Saint) on Aug 04, 2015 at 04:39 UTC

    See grep, perldata and perlsyn.

    Why is understanding of that somewhat cryptic code important to you? Maybe you should be asking some other question?

    Premature optimization is the root of all job security
Re: Unable to Understand grep and hash use for prime no.
by vinoth.ree (Monsignor) on Aug 04, 2015 at 04:48 UTC

    what you did not understand from the above code ?

    Don't you know exists $is_prime{$_} part checks whether a key exists in a hash or not.

    Don't you know $is_prime{$_} checks a value with the key in hash is true.(assuming your is_prime() function Boolean value(True or False))


    All is well. I learn by answering your questions...
Re: Unable to Understand grep and hash use for prime no.
by anonymized user 468275 (Curate) on Aug 04, 2015 at 11:27 UTC
    Finding out if a number is prime has the typical algorithm of testing all integers less than the square root of the number for whether they are a factor (and of course eliminating a perfect square). The author is trying to trade off storage for execution time by saving previous calculations as a hash (key = number, value = boolean for whether prime). I have some thoughts:

    (1) only prime factors need to be tested as factors and so test factors (all of them used per test) should also have their results kept in the lookup, so the lookup storage belongs to the function 'is_prime' (could be a package variable) rather than held at the scope shown in the snippet.

    (2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage.

    One world, one people

      (2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage.

      What you describe is a primes sieve. One common prime generation technique is the Sieve of Eratosthenes. Another (sometimes slightly faster, but always more complicated) is the Sieve of Atkin.

      I believe danaj has a blazing fast segmented sieve in Math::Prime::Util, and I have a pretty basic non-segmented Sieve of Eratosthenes implementation in Math::Prime::FastSieve.


      Dave

        Yes that's right, Dave. Coincidentally the sieve technique came up here only three weeks ago when a poster was trying to check a conjecture about Recaman's sequence. In thinking about primes, I did consider XS and C++ funnily enough, until I realised that prime or not is conceptually boolean and can be packed down to bits, so XS and C++ might be less urgent. Nevertheless I totally applaud the work you've done and XS and C++ is a very good choice.

        One world, one people

      In this case, the example is simply trying to show that results can be cached. As you say, we could reduce storage cost a lot and speed a little by using an array, string, or vector. Though one has to be careful with that as a single input of (for example) 1e18 will work fine with the hash but blow up with the other methods.

      It turns out using a module (e.g. ntheory) for is_prime() is easier and faster overall anyway. No need to spend time on sieving, caching, memoize, etc. for these small sizes. But looking at the full context for this code, this is completely backwards -- he's using primality as a simple test vehicle to show caching.

        That's why Davido's module uses XS and C++. An optimised Perl implementation would have a challenge to re-invent the processor in some ways, whereas in C++, structs can be used to map one datatype over another without any conversion, bit-shifting or reassignment making it easier to simulate a 2^N bit machine, where N is arbitrary.

        One world, one people

Re: Unable to Understand grep and hash use for prime no.
by ikegami (Pope) on Aug 04, 2015 at 18:46 UTC
    It's a version of
    @primes = grep { is_prime($_) } @numbers;
    that caches the results of calls to is_prime to avoid calling it more than once with the same input. It trades off memory in an attempt to speed up the process.
Re: Unable to Understand grep and hash use for prime no.
by Anonymous Monk on Aug 04, 2015 at 03:14 UTC

    I'm unable to understand what exactly this code doing: exists $is_prime{$_} and $is_prime{$_}

    Do you have any guesses?

    Can you identify/name any part of the code as a type of thing (ex: variable , scalar...)?

Re: Unable to Understand grep and hash use for prime no.
by soonix (Canon) on Aug 04, 2015 at 18:59 UTC
    my %is_prime; @primes = grep { ( exists $is_prime{$_} and $is_prime{$_} ) or ( $is_prime{$_} = is_prime($_) ) } @numbers;
    Do I understand correctly that for numbers where $is_prime{$_} is false, the cached value is overwritten by a (supposedly superfluous) evaluation of is_prime($_)?
A reply falls below the community's threshold of quality. You may see it by logging in.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1137324]
Approved by GrandFather
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (6)
As of 2021-11-30 00:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?