Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #24289 > unrolled thread

Java 8 Streams and Eratosthenes

Back to article view | Back to comp.lang.java.programmer

Contents

  Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-04 23:54 +0200
    Re: Java 8 Streams and Eratosthenes Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-04 19:35 -0300
      Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:03 +0200
        Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:44 +0200
          Re: Java 8 Streams and Eratosthenes Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-05 17:43 -0300
            Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-10 01:27 +0200
              Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-09 22:28 -0300
                Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-10 19:43 +0200
                  Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-10 13:18 -0700
                    Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-11 23:27 +0200
                      Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 10:32 +0200
                      Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 14:37 +0200
                        Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-12 12:05 -0700
                          Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-12 22:53 +0200
                        Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) markspace <markspace@nospam.nospam> - 2013-06-15 15:18 -0700
                          Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-16 22:52 +0200
                          Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Arved Sandstrom <asandstrom2@eastlink.ca> - 2013-06-16 21:56 -0300
                          Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes) Sebastian <news@seyweiler.dyndns.org> - 2013-06-18 23:18 +0200
    Re: Java 8 Streams and Eratosthenes markspace <markspace@nospam.nospam> - 2013-06-04 17:24 -0700
      Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:09 +0200
        Re: Java 8 Streams and Eratosthenes markspace <markspace@nospam.nospam> - 2013-06-05 09:45 -0700
          Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 21:32 +0200
      Re: Java 8 Streams and Eratosthenes Sebastian <news@seyweiler.dyndns.org> - 2013-06-05 09:47 +0200

Page 2 of 2 — ← Prev page 1 [2]

#24307

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.

[toc] | [prev] | [next] | [standalone]

#24310

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

[toc] | [prev] | [next] | [standalone]

#24303

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

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web