Java 8 Streams and Eratosthenes

S

Sebastian

Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.

However, things were made difficult by the fact that Stream#findFirst()
is a terminal (and short-circuiting) operation, so I couldn't use it
to access the first stream element to incrementally build a result.
The solution shown below uses an additional storage for these elements,
and finds out which of the elements passing through the stream are new
primes by counting them at each stage. This works, but it is certainly
not something to show your functional programming friends.

I'd be grateful for suggestions for improvement, or other solutions.
I'd also like to know how this could be enhanced to generate an
infinite stream of primes (i. e. when the upper bound n is unknown and
new filters may need to be generated on the fly). I could imagine a
solution if it were possible to "pipe" one stream into another, but that
doesn't seem to be possible.

Perhaps the lesson is that some things are best not done using
streams. I also include a Java7 while-loop version of the same below.
This is more concise, clearer and easily generalizes to an infinite
stream. (However, it is eager, not lazy, and would take some more effort
to convert to a lazy solution, probably involving Callbacks and perhaps
losing its conciseness.)

What are your opinions?

Best,
Sebastian

Code follows. This has been tested to compile and run with lambda b88.
======================================================================

public void primes(int n) {
List<Integer> primes = new ArrayList<>();
Stream<Integer> s = Stream.iterate(2, x -> x + 1);
for (int i = 0; i < n; i++) {
int k = i;
Consumer<Integer> kthPrime = kthPrime(k, primes);
s = s.peek(kthPrime).filter(x -> {int p = currPrime(k,primes);
return x == p || x % p != 0;});
}
assert primes.isEmpty();
s.limit(n).forEach(x -> System.out.print(x + " "));
assert primes.size() == n;
}

/**
* Find the prime that is used in the kth filter. That is the kth prime
* if it has been discovered yet, otherwise it is a smaller prime that
* is currently passing throgh the stream and must be let through the
* filter.
* @param k the filter number
* @param primes the list of primes
* @return the largest prime with an index less than or equal to k
*/
private Integer currPrime(int k, List<Integer> primes) {
return primes.get(min(k,primes.size()-1));
}

/**
* Mark the kth prime number for reference in a subsequent filter.
* @param k the prime number index
* @param primes the list of primes
* @return a consumer that puts the kth integer that comes its way
* into the specified list of primes
*/
private Consumer<Integer> kthPrime(int k, List<Integer> primes) {
return new Consumer<Integer>() {
private int idx;

@Override
public void accept(Integer p) {
if (idx > k) return;
if (idx == k) primes.add(p);
idx++;
}
};
}

/**
* For comparison, here is a Java 7 version of the prime generator.
* @param n limit on the number of primes
*/
public void primesJava7(int n) {
List<Integer> primes = new ArrayList<>();
int x = 2;
while (primes.size() < n) {
boolean isPrime = true;
for (Iterator<Integer> it = primes.iterator();
isPrime && it.hasNext();) {
if (x % it.next() == 0) isPrime = false;
}
if (isPrime) primes.add(x);
x++;
}
System.out.println(primes);
}
 
A

Arved Sandstrom

Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.

However, things were made difficult by the fact that Stream#findFirst()
is a terminal (and short-circuiting) operation, so I couldn't use it
to access the first stream element to incrementally build a result.
The solution shown below uses an additional storage for these elements,
and finds out which of the elements passing through the stream are new
primes by counting them at each stage. This works, but it is certainly
not something to show your functional programming friends.

I'd be grateful for suggestions for improvement, or other solutions.
I'd also like to know how this could be enhanced to generate an
infinite stream of primes (i. e. when the upper bound n is unknown and
new filters may need to be generated on the fly). I could imagine a
solution if it were possible to "pipe" one stream into another, but that
doesn't seem to be possible.

Perhaps the lesson is that some things are best not done using
streams. I also include a Java7 while-loop version of the same below.
This is more concise, clearer and easily generalizes to an infinite
stream. (However, it is eager, not lazy, and would take some more effort
to convert to a lazy solution, probably involving Callbacks and perhaps
losing its conciseness.)

What are your opinions?

Best,
Sebastian
[ SNIP ]

Some things are best not done using Java. Given interop, I'd use Closure
or Scala for this type of stuff, if the main program is still Java.

AHS
 
M

markspace

Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.


I don't think it's plausible or a good implementation. The point of
this particular sieve is that it relies on easily skipping past values
and only accessing the one's you want. For example, in an array, you
can easily compute the even numbers by adding +2 to the previous offset.
Multiples of 3 are found by adding +3 to the previous offset. Etc.

In order to determine if n is prime, you have to run n filters on all
previous values of n. This seems inefficient.

With streams, you have to account for the fact that the previous sieve
has already removed a lot of values. (I assume; I'm no expert on Java
lambdas.) How do you even do that? I don't know.

I think I agree with your conclusion that "Perhaps the lesson is that
some things are best not done using streams." That's likely the case imo.

Perhaps a better candidate is BigInteger#nextProbablePrime().
 
S

Sebastian

Am 05.06.2013 00:35, schrieb Arved Sandstrom:
Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.
[snip]

Perhaps the lesson is that some things are best not done using
streams. [snip]

What are your opinions?

Best,
Sebastian
[ SNIP ]

Some things are best not done using Java. Given interop, I'd use Closure
or Scala for this type of stuff, if the main program is still Java.

AHS

That's a bit of a dodge, isn't it? Scala may be a nice language, but
that doesn't help with investigating Java's strength and weaknesses.

-- Sebastian
 
S

Sebastian

Am 05.06.2013 02:24, schrieb markspace:
I don't think it's plausible or a good implementation. The point of this
particular sieve is that it relies on easily skipping past values and
only accessing the one's you want. For example, in an array, you can
easily compute the even numbers by adding +2 to the previous offset.
Multiples of 3 are found by adding +3 to the previous offset. Etc.

In order to determine if n is prime, you have to run n filters on all
previous values of n. This seems inefficient.

but not more inefficient than multiple passes over an array. However, my
issue wasn't so much with the efficiency of the implementation (nor
with its correctness - it is correct), but with its style.
With streams, you have to account for the fact that the previous sieve
has already removed a lot of values. (I assume; I'm no expert on Java
lambdas.) How do you even do that? I don't know.

that's taken care of by the chaining of the filters. One problem with
the implementation is that one has to build the entire filter chain up
front, as it doesn't seem to be possible to add filters to a stream
once it has been operated on.
I think I agree with your conclusion that "Perhaps the lesson is that
some things are best not done using streams." That's likely the case imo.

Perhaps a better candidate is BigInteger#nextProbablePrime().
thanks for the idea. I'll go look at it.

-- Sebastrian
 
S

Sebastian

Am 05.06.2013 09:03, schrieb Sebastian:
Am 05.06.2013 00:35, schrieb Arved Sandstrom:
Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.
[snip]

Perhaps the lesson is that some things are best not done using
streams. [snip]

What are your opinions?

Best,
Sebastian
[ SNIP ]

Some things are best not done using Java. Given interop, I'd use Closure
or Scala for this type of stuff, if the main program is still Java.

AHS

That's a bit of a dodge, isn't it? Scala may be a nice language, but
that doesn't help with investigating Java's strength and weaknesses.

-- Sebastian

Or perhaps it does. There are many Scala implementations of this
algorithm on the internet, cf. this one

def primes : Stream[Int] = {

var is = Stream from 2

def sieve(numbers: Stream[Int]): Stream[Int] = {
Stream.cons(
numbers.head,
sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
}

sieve(is)
}

from
http://louisbotterill.blogspot.de/2009/07/scala-lazy-evaluation-and-sieve-of.html

What the implementations all seem to have in common is the ability to
access the head of the stream and still lazily operate on the rest. It
is an ability that Java streams lack. So perhaps the way to go is to
create a sort of LazyLinkedList in Java (if there isn't one.)

-- Sebastian
 
S

Sebastian

Am 05.06.2013 02:24, schrieb markspace:
I don't think it's plausible or a good implementation. The point of this
particular sieve is that it relies on easily skipping past values and
only accessing the one's you want. For example, in an array, you can
easily compute the even numbers by adding +2 to the previous offset.
Multiples of 3 are found by adding +3 to the previous offset. Etc.

Indeed, it may be said that this particular implementation (and many
others often presented as the Sieve of Eratosthenes) really isn't the
sieve, but just a naive version of trial division. Cf. this paper by
Melissa E. O’Neil: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

But as I said before, that wasn't really my point.

-- Sebastian
 
M

markspace

that's taken care of by the chaining of the filters. One problem with

How does that actually work though? I'm not familiar with the details
of filters.

For example if you have a stream of integers:

1 2 3 4 5 6 7 8 9 10 11 12 13...

And you sieve out all the even ones after the first:

1 2 3 5 7 9 11 13...

And then you try to sieve out all the multiples of 3 after the first:

1 2 3 5 7 9 11 13 15...
^
position '6'

The position of the '6' in the sieve is shifted to be the actual number
9. I don't see how the sieve is going to work like that. It gets more
obviously worse as you add more filters.

1 2 3 5 7 11 13 17 ...

For example sieving '4' is going to remove 17 here, and that's not
right, 17 is prime.
 
S

Sebastian

Am 05.06.2013 18:45, schrieb markspace:
How does that actually work though? I'm not familiar with the details of
filters.

For example if you have a stream of integers:

1 2 3 4 5 6 7 8 9 10 11 12 13...

And you sieve out all the even ones after the first:

1 2 3 5 7 9 11 13...

And then you try to sieve out all the multiples of 3 after the first:

1 2 3 5 7 9 11 13 15...
^
position '6'

The position of the '6' in the sieve is shifted to be the actual number
9. I don't see how the sieve is going to work like that. It gets more
obviously worse as you add more filters.

1 2 3 5 7 11 13 17 ...

For example sieving '4' is going to remove 17 here, and that's not
right, 17 is prime.
Well, yes, the algorithm doesn't work like that - it's not really a
sieve, it's a version of trial division (cf. the Melissa E. O’Neil:
reference in one of my other posts) which checks the primality of x by
testing its divisibility by each of the primes less than x. There is
no actual crossing off or sieving out going on.

If you're interested in Java 8 stream filters, just get NetBeans or
IntelliJ Idea plus the JDK from http://jdk8.java.net/lambda/
and start experimenting.

-- Sebastian
 
A

Arved Sandstrom

Am 05.06.2013 09:03, schrieb Sebastian:
Am 05.06.2013 00:35, schrieb Arved Sandstrom:
On 06/04/2013 06:54 PM, Sebastian wrote:
Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.
[snip]

Perhaps the lesson is that some things are best not done using
streams. [snip]

What are your opinions?

Best,
Sebastian
[ SNIP ]

Some things are best not done using Java. Given interop, I'd use Closure
or Scala for this type of stuff, if the main program is still Java.

AHS

That's a bit of a dodge, isn't it? Scala may be a nice language, but
that doesn't help with investigating Java's strength and weaknesses.

-- Sebastian

Or perhaps it does. There are many Scala implementations of this
algorithm on the internet, cf. this one

def primes : Stream[Int] = {

var is = Stream from 2

def sieve(numbers: Stream[Int]): Stream[Int] = {
Stream.cons(
numbers.head,
sieve(for (x <- numbers.tail if x % numbers.head > 0) yield x))
}

sieve(is)
}

from
http://louisbotterill.blogspot.de/2009/07/scala-lazy-evaluation-and-sieve-of.html


What the implementations all seem to have in common is the ability to
access the head of the stream and still lazily operate on the rest. It
is an ability that Java streams lack. So perhaps the way to go is to
create a sort of LazyLinkedList in Java (if there isn't one.)

-- Sebastian
Me I wouldn't re-invent the wheel in this case. Implementing this type
of laziness is not that straightforward.

And why not use interop between JVM languages? This way you leverage the
strengths. I usually have Java as the main language, but for some
functionality in some apps I use Scala. Maintainability goes up, for
starters, as does reliability and speed of development.

It's all ultimately JVM bytecode.

AHS
 
S

Sebastian

Am 05.06.2013 22:43, schrieb Arved Sandstrom:
On 06/05/2013 04:44 AM, Sebastian wrote: [snip]Me I wouldn't re-invent the wheel in this case. Implementing this type
of laziness is not that straightforward.

And why not use interop between JVM languages? This way you leverage the
strengths. I usually have Java as the main language, but for some
functionality in some apps I use Scala. Maintainability goes up, for
starters, as does reliability and speed of development.

It's all ultimately JVM bytecode.

AHS

It's not everyone has a management who sees it this way. In our large
project (we're talking several hundred developers and a really
complicated build process), I don't see anyone advocating more
complexity by adding another compiler and language.

Anyway, it's turned out not to be too complicated in straight Java.
One can simply extend a straightforward implementation of the usual
cons-list with the following features, giving one a
FilterableConsList<T>:
a) accept a Function<T> to generate the elements in the tail
in sequence
b) accept a Supplier<FilterableConsList<T>> to supply a tail
c) accept a Predicate<T> to filter out non-matching elements
from the tail
and make the implementation class LazyConsList<T> lazy for the tail
(but eager for the head).

It's also easy to implement AbstractCollection by providing an iterator
and make the thing streamable by providing a spliterator of unknown
size.

With that, the driver for generating the first 100 primes becomes:

LazyConsList<Integer> s = sieve(LazyConsList.newList(2, x -> x + 1));
s.stream().limit(100).forEach(x->System.out.print(x + " "));

where the interesting sieve() method is defined like this:

private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
Integer p = s.head();
return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
}

Now I think that looks pretty neat (and almost exactly like the
corresponding Scala code.)

-- Sebastian
 
A

Arved Sandstrom

Am 05.06.2013 22:43, schrieb Arved Sandstrom:
On 06/05/2013 04:44 AM, Sebastian wrote: [snip]Me I wouldn't re-invent the wheel in this case. Implementing this type
of laziness is not that straightforward.

And why not use interop between JVM languages? This way you leverage the
strengths. I usually have Java as the main language, but for some
functionality in some apps I use Scala. Maintainability goes up, for
starters, as does reliability and speed of development.

It's all ultimately JVM bytecode.

AHS

It's not everyone has a management who sees it this way. In our large
project (we're talking several hundred developers and a really
complicated build process), I don't see anyone advocating more
complexity by adding another compiler and language.

Anyway, it's turned out not to be too complicated in straight Java.
One can simply extend a straightforward implementation of the usual
cons-list with the following features, giving one a
FilterableConsList<T>:
a) accept a Function<T> to generate the elements in the tail
in sequence
b) accept a Supplier<FilterableConsList<T>> to supply a tail
c) accept a Predicate<T> to filter out non-matching elements
from the tail
and make the implementation class LazyConsList<T> lazy for the tail
(but eager for the head).

It's also easy to implement AbstractCollection by providing an iterator
and make the thing streamable by providing a spliterator of unknown
size.

With that, the driver for generating the first 100 primes becomes:

LazyConsList<Integer> s = sieve(LazyConsList.newList(2, x -> x + 1));
s.stream().limit(100).forEach(x->System.out.print(x + " "));

where the interesting sieve() method is defined like this:

private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
Integer p = s.head();
return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
}

Now I think that looks pretty neat (and almost exactly like the
corresponding Scala code.)

-- Sebastian
It does look reasonably nice, I must admit. :) I'll have to return to
Java 8 experiments and I think I'll start with a variant of your code.

I hear you when you talk about a large project with hundreds of
developers. I've worked in a number of environments like that, and in my
experience that kind of management myopia, fear and ignorance creeps in
with just a 10 or 20 person developer team, doesn't have to be hundreds.
Most managers I have encountered in close to 30 years of software
development have never programmed themselves; they are clueless. They
read in a book or article that having multiple languages in play is bad,
and avoid JNI or a second JVM language with interop like the
plague...but don't bat an eyelash at accepting entirely new technologies
or architectures that they can't find enough qualified people for. So
long as the entirely new stuff is based on Java I guess the working
assumption - hopelessly naive and ludicrous - is that any Java developer
will get it right away.

I am fortunate enough as a very senior consultant (very senior means
that you can converse about having used punched cards :)) to mostly
work gigs now where I can dictate architecture, design and
implementation. I also now - where I can - avoid projects that involve
more than one architect/designer (who is also a skilled coder *), 2-3
developers, a great BA, and a good QA/QC person. I've found that a
skilled team this size outperforms a 20-30 person team easily, 9 times
out of 10.

More specifically, what really is the complexity of introducing some
Clojure or Scala compared to requiring that your developers master new
Java APIs? I've seen considerably more project problems due to imperfect
understanding of JPA 1.x/2.x, or IO/NIO, or web services and WSDLs, or
RMI, or concurrency - all Java - than any problems caused by
implementing logic in a language better suited for it than Java.

AHS

* Not usually the case in my experience. I have no idea what process
anoints a majority of the "architects" out there, but it's not
programming skills.
 
S

Sebastian

Am 10.06.2013 03:28, schrieb Arved Sandstrom:
Am 05.06.2013 22:43, schrieb Arved Sandstrom:
Me I wouldn't re-invent the wheel in this case. Implementing this type
of laziness is not that straightforward.

And why not use interop between JVM languages? This way you leverage the
strengths. I usually have Java as the main language, but for some
functionality in some apps I use Scala. Maintainability goes up, for
starters, as does reliability and speed of development.

It's all ultimately JVM bytecode.

AHS

It's not everyone has a management who sees it this way. In our large
project (we're talking several hundred developers and a really
complicated build process), I don't see anyone advocating more
complexity by adding another compiler and language.
[snip]

private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
Integer p = s.head();
return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
}

Now I think that looks pretty neat (and almost exactly like the
corresponding Scala code.)

-- Sebastian
It does look reasonably nice, I must admit. :) I'll have to return to
Java 8 experiments and I think I'll start with a variant of your code.

If you wish, just send me an email and I'll send you my code
privately as a point of departure. I don't wish to put it on
a public site, however.

[snip]
or architectures that they can't find enough qualified people for. So
long as the entirely new stuff is based on Java I guess the working
assumption - hopelessly naive and ludicrous - is that any Java developer
will get it right away.

That is very often true. And because of that mind-set, often not enough
time is set aside for developers to test new technology in a project
context, build prototypes etc.
I am fortunate enough as a very senior consultant (very senior means
that you can converse about having used punched cards :)) to mostly
work gigs now where I can dictate architecture, design and
implementation. I also now - where I can - avoid projects that involve
more than one architect/designer (who is also a skilled coder *), 2-3
developers, a great BA, and a good QA/QC person. I've found that a
skilled team this size outperforms a 20-30 person team easily, 9 times
out of 10.

I have also found that small focused groups of up to 8 people can
achieve amazing results when protected from outside interference.
Whenever possible, we try to split up in teams about that size.
Architecture and QA are usually orthogonal to that.
More specifically, what really is the complexity of introducing some
Clojure or Scala compared to requiring that your developers master new
Java APIs?

It's not just the amount of complexity, its also where it lies - just
development, or also build process, configuration management, deployment
infrastructure setup (conventions for IDE settings etc.) If it were just
learning a new language - most developers love to do that.

I've seen considerably more project problems due to imperfect
understanding of JPA 1.x/2.x, or IO/NIO, or web services and WSDLs, or
RMI, or concurrency - all Java - than any problems caused by
implementing logic in a language better suited for it than Java.

Quite true. If you don't know hat you're doing, you're bound to screw up
in any language. With some things, however, it's not just API knowledge.
Concurrency, for example, I believe to be an intrinsically difficult
subject.
AHS

* Not usually the case in my experience. I have no idea what process
anoints a majority of the "architects" out there, but it's not
programming skills.

Do you know Simon Brown's work in progress "Software Architecture for
Developers"? (https://leanpub.com/software-architecture-for-developers)
Among other things it's about how coding is part of architecture, and
what is "just enough" design. Entertaining read.

-- Sebastian
 
M

markspace

If you wish, just send me an email and I'll send you my code
privately as a point of departure. I don't wish to put it on
a public site, however.


That's too bad, since Java 8 is new and we could use some examples how
to implement algorithms with lambda.

I assume you don't want to post the code because it's actually owned by
your employer. Would you consider posting a scaled down example on a
personal blog? Something that outlines how to solve this type of
problem without actually revealing all the details? I found what you
did post to be kind of hard to follow.

Or if you can find some public code that does something similar, base
your public post on that, and show where improvements and adaptations
can be made.

I've seen this done professionally. Neal Gafter, for example, didn't
agree with all of the patent transfer stuff on the lambda dev list, so
he often blogged his comments elsewhere and then provided a link and a
summary to the list. It's just a way of maintain rights to material
(publicly or privately) independent of an employer.
 
S

Sebastian

Am 10.06.2013 22:18, schrieb markspace:
That's too bad, since Java 8 is new and we could use some examples how
to implement algorithms with lambda.
[snip]

I found what you did post to
be kind of hard to follow.
[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
 
S

Stefan Ram

Sebastian said:
would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/

This says:

»Capture of local variables is restricted to those that
are effectively final. Lifting this restriction would
present implementation difficulties«.

Here's another story:

»Guy Steele wrote:

Actually, the prototype implementation *did* allow
non-final variables to be referenced from within
inner classes. There was an outcry from *users*,
complaining that they did not want this!«

http://madbean.com/2003/mb2003-49/
 
S

Sebastian

Am 12.06.2013 01:17, schrieb Stefan Ram:
This says:

»Capture of local variables is restricted to those that
are effectively final. Lifting this restriction would
present implementation difficulties«.

Here's another story:

»Guy Steele wrote:

Actually, the prototype implementation *did* allow
non-final variables to be referenced from within
inner classes. There was an outcry from *users*,
complaining that they did not want this!«

http://madbean.com/2003/mb2003-49/
Brian Goetz gives concurrency issues as the reason in his "official"
State of the lambda, section 7:

"It is our intent to prohibit capture of mutable local variables. The
reason is that idioms like this:

int sum = 0;
list.forEach(e -> { sum += e.size(); });

are fundamentally serial; it is quite difficult to write lambda bodies
like this that do not have race conditions. Unless we are willing to
enforce—preferably at compile time—that such a function cannot escape
its capturing thread, this feature may well cause more trouble than it
solves."

http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-4.html
 
S

Sebastian

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/

The second part is short and summarizes the content of this thread, plus
it gives the complete coding example.

The first part is more academic, perhaps suitable for use in
introductory courses.

I'd much appreciate any feedback. Either in the blog, or on this list.

-- Sebastian
 
M

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

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

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

Forum statistics

Threads
473,704
Messages
2,569,333
Members
44,615
Latest member
neveseexick

Latest Threads

Top