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.
[download]

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($_) )
}
[download]

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{$_}
[download]

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{$_}
[download]

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($_)
[download]

. . . 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
[download]

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

Hope this helps.

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

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

exists $is_prime{$_} and $is_prime{$_}
[download]

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__
[download]

See grep, perldata and perlsyn.

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

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

(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

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

@primes = grep { is_prime($_) } @numbers;
[download]

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

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