Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes)
Am 16.06.2013 00:18, schrieb markspace:
[snip]
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.)
[snip]
In her paper, O'Neill describes how the algorithm can be made much
faster by ignoring the even numbers (I'll leave out the stuff about
"wheels"). I have slightly edited your code to fit in that optimization.
I've renamed the Pair-class to "Composite" the better to show its
intended meaning, namely to represent composite numbers that are
crossed off the list. In addition to the prime factor, one needs a
third field to store the next increment. (That represents the
"map(*p)" in O'Neill's Haskell code).
The sieve predicate needs to depend on the way the candidates are
generated, in such a way that no modifications to the predicate are
necessary when that input changes. So we need to give the lambda
expression used to generate the stream wider scope.
Finally, we need to generate a stream of only the odd numbers starting
at 3. The prime 2 is not part of the stream, it must be included in the
output manually (or one could use the Lazy list util, but that's clearly
overkill.)
Note that the limit() must be set after the filter(), otherwise we would
not generate the first n primes, but the primes in the intervall [2,n]
(I like that flexibility about streams and their "fluid" API.)
O'Neill claims an improvement in execution time by a factor of about
three for PriorityQueue on Odd Numbers over simple PriorityQueue,
when generatig a few ten-thousand primes. I have not been able to
reproduce that result with this code. Probably it's the output to
System.out that swamps everything.
-- Sebastian
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.
[code snipped]
Dito. Edited code follows:
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;
/**
* A simple lambda implementation of the sieve of Eratosthenes, with
* optimizations described in
*
http://www.cs.tufts.edu/~nr/comp150fp/archive/melissa-oneill/Sieve-JFP.pdf
*
* June 18, 2013
*
* @author Brenden Towey, Sebastian Millies
*/
public class Eratosthenes {
public static void main(String[] args) {
primes(100);
}
/** A composite number represented as a multiple of some prime
factor. */
private static class Composite implements Comparable<Composite> {
public Composite(int factor, int base) {
this.number = factor * base;
this.factor = factor;
this.base = base;
}
final int number; // the composite number
final int factor; // the prime factor
final int base; // the remainder
@Override
public int compareTo(Composite other) {
return Integer.compare(number, other.number);
}
}
static void primes(int n) {
UnaryOperator<Integer> nextInt = x -> x + 2;
Predicate<Integer> sieve = new Predicate<Integer>() {
Queue<Composite> composites = new PriorityQueue<>();
@Override
public boolean test(Integer candidate) {
boolean prime = composites.isEmpty() ? true
: composites.peek().number != candidate;
if (prime) {
composites.offer(
new Composite(candidate, candidate));
} else {
while (!composites.isEmpty()
&& composites.peek().number == candidate) {
Composite cp = composites.poll();
composites.offer(new Composite(
cp.factor, nextInt.apply(cp.base)));
}
}
return prime;
}
};
System.out.println(2);
Stream.iterate(3, nextInt)
.filter(sieve)
.limit(n)
.forEach(x -> System.out.println(x));
}
}