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

Groups > comp.lang.java.programmer > #24455

Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes)

Show all headers | View raw

Am 16.06.2013 00:18, schrieb markspace:
[snip]
>
> 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.)
>
[snip]
In her paper, O'Neill describes how the algorithm can be made much
faster by ignoring the even numbers (I'll leave out the stuff about
"wheels"). I have slightly edited your code to fit in that optimization.

I've renamed the Pair-class to "Composite" the better to show its
intended meaning, namely to represent composite numbers that are
crossed off the list. In addition to the prime factor, one needs a
third  field to store the next increment. (That represents the
"map(*p)" in O'Neill's Haskell code).

The sieve predicate needs to depend on the way the candidates are
generated, in such a way that no modifications to the predicate are
necessary when that input changes. So we need to give the lambda
expression used to generate the stream wider scope.

Finally, we need to generate a stream of only the odd numbers starting
at 3. The prime 2 is not part of the stream, it must be included in the
output manually (or one could use the Lazy list util, but that's clearly
overkill.)

Note that the limit() must be set after the filter(), otherwise we would
not generate the first n primes, but the primes in the intervall [2,n]
(I like that flexibility about streams and their "fluid" API.)

O'Neill claims an improvement in execution time by a factor of about
three for PriorityQueue on Odd Numbers over simple PriorityQueue,
when generatig a few ten-thousand primes. I have not been able to
reproduce that result with this code. Probably it's the output to
System.out that swamps everything.

-- Sebastian

>
> 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.
>
[code snipped]

Dito. Edited code follows:

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;

/**
  * A simple lambda implementation of the sieve of Eratosthenes, with
  * optimizations described in
  * 
http://www.cs.tufts.edu/~nr/comp150fp/archive/melissa-oneill/Sieve-JFP.pdf
  *
  * June 18, 2013
  *
  * @author Brenden Towey, Sebastian Millies
  */
public class Eratosthenes {

     public static void main(String[] args) {
         primes(100);
     }

     /** A composite number represented as a multiple of some prime
         factor. */
     private static class Composite implements Comparable<Composite> {

         public Composite(int factor, int base) {
             this.number = factor * base;
             this.factor = factor;
             this.base = base;
         }

         final int number; // the composite number
         final int factor; // the prime factor
         final int base;   // the remainder

         @Override
         public int compareTo(Composite other) {
             return Integer.compare(number, other.number);
         }
     }

     static void primes(int n) {

         UnaryOperator<Integer> nextInt = x -> x + 2;

         Predicate<Integer> sieve = new Predicate<Integer>() {
             Queue<Composite> composites = new PriorityQueue<>();

             @Override
             public boolean test(Integer candidate) {
                 boolean prime = composites.isEmpty() ? true
                                 : composites.peek().number != candidate;
                 if (prime) {
                     composites.offer(
                         new Composite(candidate, candidate));
                 } else {
                     while (!composites.isEmpty()
                            && composites.peek().number == candidate) {
                         Composite cp = composites.poll();
                         composites.offer(new Composite(
                             cp.factor, nextInt.apply(cp.base)));
                     }
                 }
                 return prime;
             }
         };

         System.out.println(2);
         Stream.iterate(3, nextInt)
                 .filter(sieve)
                 .limit(n)
                 .forEach(x -> System.out.println(x));
     }
}

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web