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

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

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

Re: Java 8 Streams and EratosthenesOn 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(). |

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

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

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

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

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

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

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