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

Groups > comp.lang.java.programmer > #24420

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

Show key headers only | View raw

On 6/12/2013 5:37 AM, Sebastian wrote:
> Am 11.06.2013 23:27, schrieb Sebastian:
> [snip]
>>
>> I have thought again, and will put something together on a blog. May
>> take a day or two, I'll be back to post a link. It will still be hard
>> to follow, though. Meanwhile, a good place to get started with the topic
>> would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/
>>
>> -- Sebastian
>
> I have written two blog entries about higher-order functions with Java 8
> lambda expressions. They can be found at
>
> http://sebastian-millies.blogspot.de/

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-04 23:54 +0200
  Re: Java 8 Streams and Eratosthenes Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-04 19:35 -0300
    Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:03 +0200
      Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:44 +0200
        Re: Java 8 Streams and Eratosthenes Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-05 17:43 -0300
          Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-10 01:27 +0200
            Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-09 22:28 -0300
              Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-10 19:43 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-10 13:18 -0700
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-11 23:27 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 10:32 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 14:37 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-12 12:05 -0700
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 22:53 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-15 15:18 -0700
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-16 22:52 +0200
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-16 21:56 -0300
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-18 23:18 +0200
  Re: Java 8 Streams and Eratosthenes markspace <markspace@nospam.nospam> - 2013-06-04 17:24 -0700
    Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:09 +0200
      Re: Java 8 Streams and Eratosthenes markspace <markspace@nospam.nospam> - 2013-06-05 09:45 -0700
        Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 21:32 +0200
    Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:47 +0200

csiph-web