Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!newsfeed.fsmpi.rwth-aachen.de!eternal-september.org!feeder.eternal-september.org!mx05.eternal-september.org!.POSTED!not-for-mail From: markspace Newsgroups: comp.lang.java.programmer Subject: Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Date: Sat, 15 Jun 2013 15:18:26 -0700 Organization: A noiseless patient Spider Lines: 246 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 15 Jun 2013 22:13:33 +0000 (UTC) Injection-Info: mx05.eternal-september.org; posting-host="5aa64ebf9a53573f97c75abba936b0e2"; logging-data="2461"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX180wUC4L3qwAcOHnkytWHkaCOeCWonSFh0=" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130509 Thunderbird/17.0.6 In-Reply-To: Cancel-Lock: sha1:ARAFvilFbMhc3HrxG00e3JE1DeY= Xref: csiph.com comp.lang.java.programmer:24420 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 sieve = new Predicate() { .... } So far so good. We need to override the test method for the Predicate: Predicate sieve = new Predicate() { @Override public boolean test( Integer candidate ) { ... } } OK, lets add the priority queue also: Predicate sieve = new Predicate() { PriorityQueue 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 sieve = new Predicate() { PriorityQueue 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 { 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 sieve = new Predicate() { PriorityQueue 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 ); } ) ; } }