Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail From: Sebastian Newsgroups: comp.lang.java.programmer Subject: Re: Java 8 Streams and Eratosthenes Date: Wed, 05 Jun 2013 09:09:43 +0200 Organization: albasani.net Lines: 43 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net s4jFM00kmch5mmPP1xTKMiwYCbgxlTrNTkAkTUZ/WVw1fuQtFwvjShuc3kGs7JjGUVPnTmu3M2Wp+ja1C4WMOA== NNTP-Posting-Date: Wed, 5 Jun 2013 07:09:35 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="Lm+8Fk0gLvhU61NfUO4SSiZE04L6pqRAuU9Gk7B/tl75DwX4nL0nRkHe6wW4cpwYmKf50SXiCS8UhtJ+Q7aJp4JIllZoYfzmgxjzD+uMY1o2tEW33QD2wpJoEimmy7Kl"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9 In-Reply-To: Cancel-Lock: sha1:9On4UId/4byI3wP2pV35Fbw63+A= Xref: csiph.com comp.lang.java.programmer:24301 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