Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes)

On 6/12/2013 5:37 AM, Sebastian wrote:


So I had a chance to look at this a bit. Lambda are kind of cool. You
can generate lists of number easily:

    static void test1() {
       Stream.iterate( 0, x -> x + 1 )
               ;
    }

This actually runs, even though the list is infinite. Many streams are
lazy, and don't evaluate unless asked for more. I guess the stream
above initializes its values, but then never generates any numbers since
it's never asked for any.

Once you have a stream you can do cool things with it. You can limit
the number of entries processed, for example, or filter them.

You can also use "terminal functions" to do things other than pass more
values back to a stream. Here forEach() is a terminal that I use to
print the results of the stream.

    static void test2() {
       Stream.iterate( 0, x -> x + 1 )
               .limit(10)
               .filter( x -> (x % 2) == 1 )
               .forEach( x -> { System.out.println( x ); } )
               ;
    }

This generates a stream, limits the total to 10, filters on the odd
numbers (leaves only the odd numbers in the stream), and then prints the
results.

So to make this print primes, we have to filter a little differently. I
really didn't understand the code in your first post, so I might be
missing some points here. But I followed the example that you linked to
earlier:

Cf. this paper by Melissa E. O???Neil:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

And I gave that a go. The trick is to define your own predicate. No,
it's not really a lambda at that point, but it does work, and with less
code than either your first example or your blog. (Although barely less.)

Here's the stream:

       Stream.iterate( 2, x -> x + 1 )
               .limit( 100 )
               .filter( sieve )
               .forEach( x -> { System.out.println( x ); } )
               ;

Pretty much the same as before, except I've got a pre-defined variable
"sieve" for a filter. What is this? Well it starts off as an anonymous
class:

       Predicate<Integer> sieve = new Predicate<Integer>() {
    ....
       }

So far so good. We need to override the test method for the Predicate:

       Predicate<Integer> sieve = new Predicate<Integer>() {
          @Override
          public boolean test( Integer candidate ) {
        ...
     }
       }

OK, lets add the priority queue also:

       Predicate<Integer> sieve = new Predicate<Integer>() {
          PriorityQueue<Pair> queue = new PriorityQueue<>();
          @Override
          public boolean test( Integer candidate ) {
        ...
     }
       }

So far this looks like a regular old anonymous class. And it is. Now
we just have to add the logic to remove primes. This doesn't require
that we have access to other parts of the stream, because we're storing
those values we care about in the priority queue. Whether that's good
design or bad design I'm not sure, although Ms. O'Neil makes hash out of
the naive algorithm in a simple Haskell implementation. So perhaps
willy-nilly access to other parts of a stream isn't such a great idea.

On the algorithm itself, if for example we find a prime at location 5,
then we know it's prime because no previous factors (2, 3) are at this
position. So we add 5 to the queue at position 10 (the next factor of
5), and as we march up the line of integers, when we reach position 10,
we see it has "5" attached to it. So we know 10 is not prime, and we
take all the factors attached to 10, and put them back in the queue at
their next position. In this example, the 5 goes back in the queue at
position 15.

The point here is that you actually need to store two numbers in the
queue: a position, and the original factor to increase the current
position by. That's why I need to create a Pair class below.

The code isn't too bad. We just take a look at the queue, if nothing is
there at our position, the number is prime.

     boolean prime = queue.peek().priority != candidate;

If the value is prime, we just add a new Pair to the queue.

     if( prime ) {
        queue.add( new Pair( candidate*candidate, candidate ) );

(An optimization Ms. O'Neil points out is that numbers can be added to
the queue as the square of their initial values. I'll leave that bit as
an exercise to the reader.)

If the value was not prime, we have some previous values to process. I
pull them out of the queue, add one more factor to their position, and
put the back in the queue. Do this until there are no more factors at
the current candidate prime location:

                while( queue.peek().priority == candidate )
                {
                   Pair p = queue.poll();
                   p.priority += p.factor;
                   queue.add( p );
                }

All this is somewhat complicated by the need to check for an empty queue
and null values.

       Predicate<Integer> sieve = new Predicate<Integer>() {

          PriorityQueue<Pair> queue = new PriorityQueue<>();

          @Override
          public boolean test( Integer candidate ) {
             boolean prime = (queue.peek() != null ) ?
                   queue.peek().priority != candidate : true ;
             if( prime ) {
                queue.add( new Pair( candidate*candidate, candidate ) );
             } else {
                while( queue.peek()!= null &&
                        queue.peek().priority == candidate )
                {
                   Pair p = queue.poll();
                   p.priority += p.factor;
                   queue.add( p );
                }
             }
             return prime;
          }

       };

Well that's a fair amount of code, but not too bad really if you
consider other examples that work the same way. This code is slightly
edited for the web, I hope I didn't introduce any typos.

package sieve;

import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.stream.Stream;
import java.util.function.Predicate;

/**
  * A simple lambda implementation of the sieve of
  * Eratosthenes.
  *
  * June 15, 2013
  *
  * @author Brenden Towey
  */
public class Eratosthenes
{

    public static void main( String[] args )
    {
       test4();
    }

    private static class Pair implements Comparable<Pair>
    {
       public Pair( int priority, int factor )
       {
          this.priority = priority;
          this.factor = factor;
       }
       int priority;
       int factor;
       @Override
       public int compareTo( Pair pair ) {
          return Integer.compare( priority, pair.priority );
       }
    }

    static void test4() {

       Predicate<Integer> sieve = new Predicate<Integer>() {
          PriorityQueue<Pair> queue = new PriorityQueue<>();
          @Override
          public boolean test( Integer candidate ) {
             boolean prime = (queue.peek() != null ) ?
                   queue.peek().priority != candidate : true ;
             if( prime ) {
                queue.add( new Pair( candidate*candidate, candidate ) );
             } else {
                while( queue.peek()!= null &&
                        queue.peek().priority == candidate )
                {
                   Pair p = queue.poll();
                   p.priority += p.factor;
                   queue.add( p );
                }
             }
             return prime;
          }
       };

       Stream.iterate( 2, x -> x + 1 )
               .limit( 100 )
               .filter( sieve )
               .forEach( x -> { System.out.println( x ); } )
               ;
    }
}