Java 8 Streams and Eratosthenes

S

Sebastian

Am 16.06.2013 00:18, schrieb markspace:
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 )
;
}
yes, I think its a good thing this is being added to Java. A real advance.
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.
yes, that's how it works. By the way, streams are not only lazy, but
many tasks that work on streams can be parallelized by just calling the
parallel() method on the stream. That's explicit but unobtrusive - all
the concurrent stuff happens under the hood (based on the
fork-join-framework of Java 7). I haven't yet looked at this in detail,
though.

[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]
that's good to see. Thanks for sharing the code. It's nice having a real
sieve of Eratosthenes now. (But I still like the simple formulation of
the naive algorithm, just for its looks - although objectively it
performs worse.)

I also like your step-by-step exposition.

Best Regards,
Sebastian
 
A

Arved Sandstrom

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

Good stuff, guys, both of you. This is the kind of Java thread that
really appeals to me. You both got me motivated to get the latest Java 8
snapshot for Linux and start messing around with this stuff.

I tend to be a bit of a snob because of having used Haskell, Scala,
OCaml, LISP/Lisp, Scheme etc extensively, and F# most recently. I like
the cleaner forms where you can one-line something that even in Java 8
may take a page of code.

But it occurred to me, based on something Sebastian said, that if Java's
all you've got, and many workplaces do narrowly dictate that, then it
helps if the language and APIs have got these capabilities.

AHS
 
S

Sebastian

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,767
Messages
2,569,570
Members
45,045
Latest member
DRCM

Latest Threads

Top