Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Java 8 Streams and Eratosthenes (http://www.velocityreviews.com/forums/t961409-java-8-streams-and-eratosthenes.html)

Sebastian 06-04-2013 09:54 PM

Java 8 Streams and Eratosthenes
 
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);
}

Arved Sandstrom 06-04-2013 10:35 PM

Re: Java 8 Streams and Eratosthenes
 
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.
>
> 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
--
When a true genius appears, you can know him by this sign:
that all the dunces are in a confederacy against him.
-- Jonathan Swift

markspace 06-05-2013 12:24 AM

Re: Java 8 Streams and Eratosthenes
 
On 6/4/2013 2: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.



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().



Sebastian 06-05-2013 07:03 AM

Re: Java 8 Streams and Eratosthenes
 
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

Sebastian 06-05-2013 07:09 AM

Re: Java 8 Streams and Eratosthenes
 
Am 05.06.2013 02:24, schrieb markspace:
> On 6/4/2013 2: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.

>
>
> 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



Sebastian 06-05-2013 07:44 AM

Re: Java 8 Streams and Eratosthenes
 
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/20...-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


Sebastian 06-05-2013 07:47 AM

Re: Java 8 Streams and Eratosthenes
 
Am 05.06.2013 02:24, schrieb markspace:
> On 6/4/2013 2: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.

>
>
> 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

markspace 06-05-2013 04:45 PM

Re: Java 8 Streams and Eratosthenes
 
On 6/5/2013 12:09 AM, Sebastian wrote:
>> 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


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.



Sebastian 06-05-2013 07:32 PM

Re: Java 8 Streams and Eratosthenes
 
Am 05.06.2013 18:45, schrieb markspace:
> On 6/5/2013 12:09 AM, Sebastian wrote:
>>> 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

>
> 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

Arved Sandstrom 06-05-2013 08:43 PM

Re: Java 8 Streams and Eratosthenes
 
On 06/05/2013 04:44 AM, Sebastian wrote:
> 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/20...-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

--
When a true genius appears, you can know him by this sign:
that all the dunces are in a confederacy against him.
-- Jonathan Swift


All times are GMT. The time now is 08:56 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.