Java 8 Streams and Eratosthenes

Discussion in 'Java' started by Sebastian, Jun 4, 2013.

  1. Sebastian

    Sebastian Guest

    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);
    }
    Sebastian, Jun 4, 2013
    #1
    1. Advertising

  2. 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
    Arved Sandstrom, Jun 4, 2013
    #2
    1. Advertising

  3. Sebastian

    markspace Guest

    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().
    markspace, Jun 5, 2013
    #3
  4. Sebastian

    Sebastian Guest

    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, Jun 5, 2013
    #4
  5. Sebastian

    Sebastian Guest

    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, Jun 5, 2013
    #5
  6. Sebastian

    Sebastian Guest

    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/2009/07/scala-lazy-evaluation-and-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, Jun 5, 2013
    #6
  7. Sebastian

    Sebastian Guest

    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
    Sebastian, Jun 5, 2013
    #7
  8. Sebastian

    markspace Guest

    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.
    markspace, Jun 5, 2013
    #8
  9. Sebastian

    Sebastian Guest

    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
    Sebastian, Jun 5, 2013
    #9
  10. 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/2009/07/scala-lazy-evaluation-and-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
    Arved Sandstrom, Jun 5, 2013
    #10
  11. Sebastian

    Sebastian Guest

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

    Am 05.06.2013 22:43, schrieb Arved Sandstrom:
    > On 06/05/2013 04:44 AM, Sebastian wrote:

    [snip]
    >>

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


    It's not everyone has a management who sees it this way. In our large
    project (we're talking several hundred developers and a really
    complicated build process), I don't see anyone advocating more
    complexity by adding another compiler and language.

    Anyway, it's turned out not to be too complicated in straight Java.
    One can simply extend a straightforward implementation of the usual
    cons-list with the following features, giving one a
    FilterableConsList<T>:
    a) accept a Function<T> to generate the elements in the tail
    in sequence
    b) accept a Supplier<FilterableConsList<T>> to supply a tail
    c) accept a Predicate<T> to filter out non-matching elements
    from the tail
    and make the implementation class LazyConsList<T> lazy for the tail
    (but eager for the head).

    It's also easy to implement AbstractCollection by providing an iterator
    and make the thing streamable by providing a spliterator of unknown
    size.

    With that, the driver for generating the first 100 primes becomes:

    LazyConsList<Integer> s = sieve(LazyConsList.newList(2, x -> x + 1));
    s.stream().limit(100).forEach(x->System.out.print(x + " "));

    where the interesting sieve() method is defined like this:

    private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
    Integer p = s.head();
    return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
    }

    Now I think that looks pretty neat (and almost exactly like the
    corresponding Scala code.)

    -- Sebastian
    Sebastian, Jun 10, 2013
    #11
  12. Re: Lazy primes with Java 8 (was Re: Java 8 Streams and Eratosthenes)

    On 06/09/2013 08:27 PM, Sebastian wrote:
    > Am 05.06.2013 22:43, schrieb Arved Sandstrom:
    >> On 06/05/2013 04:44 AM, Sebastian wrote:

    > [snip]
    >>>

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

    >
    > It's not everyone has a management who sees it this way. In our large
    > project (we're talking several hundred developers and a really
    > complicated build process), I don't see anyone advocating more
    > complexity by adding another compiler and language.
    >
    > Anyway, it's turned out not to be too complicated in straight Java.
    > One can simply extend a straightforward implementation of the usual
    > cons-list with the following features, giving one a
    > FilterableConsList<T>:
    > a) accept a Function<T> to generate the elements in the tail
    > in sequence
    > b) accept a Supplier<FilterableConsList<T>> to supply a tail
    > c) accept a Predicate<T> to filter out non-matching elements
    > from the tail
    > and make the implementation class LazyConsList<T> lazy for the tail
    > (but eager for the head).
    >
    > It's also easy to implement AbstractCollection by providing an iterator
    > and make the thing streamable by providing a spliterator of unknown
    > size.
    >
    > With that, the driver for generating the first 100 primes becomes:
    >
    > LazyConsList<Integer> s = sieve(LazyConsList.newList(2, x -> x + 1));
    > s.stream().limit(100).forEach(x->System.out.print(x + " "));
    >
    > where the interesting sieve() method is defined like this:
    >
    > private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
    > Integer p = s.head();
    > return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
    > }
    >
    > Now I think that looks pretty neat (and almost exactly like the
    > corresponding Scala code.)
    >
    > -- Sebastian
    >

    It does look reasonably nice, I must admit. :) I'll have to return to
    Java 8 experiments and I think I'll start with a variant of your code.

    I hear you when you talk about a large project with hundreds of
    developers. I've worked in a number of environments like that, and in my
    experience that kind of management myopia, fear and ignorance creeps in
    with just a 10 or 20 person developer team, doesn't have to be hundreds.
    Most managers I have encountered in close to 30 years of software
    development have never programmed themselves; they are clueless. They
    read in a book or article that having multiple languages in play is bad,
    and avoid JNI or a second JVM language with interop like the
    plague...but don't bat an eyelash at accepting entirely new technologies
    or architectures that they can't find enough qualified people for. So
    long as the entirely new stuff is based on Java I guess the working
    assumption - hopelessly naive and ludicrous - is that any Java developer
    will get it right away.

    I am fortunate enough as a very senior consultant (very senior means
    that you can converse about having used punched cards :)) to mostly
    work gigs now where I can dictate architecture, design and
    implementation. I also now - where I can - avoid projects that involve
    more than one architect/designer (who is also a skilled coder *), 2-3
    developers, a great BA, and a good QA/QC person. I've found that a
    skilled team this size outperforms a 20-30 person team easily, 9 times
    out of 10.

    More specifically, what really is the complexity of introducing some
    Clojure or Scala compared to requiring that your developers master new
    Java APIs? I've seen considerably more project problems due to imperfect
    understanding of JPA 1.x/2.x, or IO/NIO, or web services and WSDLs, or
    RMI, or concurrency - all Java - than any problems caused by
    implementing logic in a language better suited for it than Java.

    AHS

    * Not usually the case in my experience. I have no idea what process
    anoints a majority of the "architects" out there, but it's not
    programming skills.
    --
    When a true genius appears, you can know him by this sign:
    that all the dunces are in a confederacy against him.
    -- Jonathan Swift
    Arved Sandstrom, Jun 10, 2013
    #12
  13. Sebastian

    Sebastian Guest

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

    Am 10.06.2013 03:28, schrieb Arved Sandstrom:
    > On 06/09/2013 08:27 PM, Sebastian wrote:
    >> Am 05.06.2013 22:43, schrieb Arved Sandstrom:
    >>> 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
    >>>

    >>
    >> It's not everyone has a management who sees it this way. In our large
    >> project (we're talking several hundred developers and a really
    >> complicated build process), I don't see anyone advocating more
    >> complexity by adding another compiler and language.
    >>

    [snip]
    >>
    >> private LazyConsList<Integer> sieve(FilterableConsList<Integer> s) {
    >> Integer p = s.head();
    >> return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
    >> }
    >>
    >> Now I think that looks pretty neat (and almost exactly like the
    >> corresponding Scala code.)
    >>
    >> -- Sebastian
    >>

    > It does look reasonably nice, I must admit. :) I'll have to return to
    > Java 8 experiments and I think I'll start with a variant of your code.


    If you wish, just send me an email and I'll send you my code
    privately as a point of departure. I don't wish to put it on
    a public site, however.

    [snip]
    > or architectures that they can't find enough qualified people for. So
    > long as the entirely new stuff is based on Java I guess the working
    > assumption - hopelessly naive and ludicrous - is that any Java developer
    > will get it right away.


    That is very often true. And because of that mind-set, often not enough
    time is set aside for developers to test new technology in a project
    context, build prototypes etc.
    >
    > I am fortunate enough as a very senior consultant (very senior means
    > that you can converse about having used punched cards :)) to mostly
    > work gigs now where I can dictate architecture, design and
    > implementation. I also now - where I can - avoid projects that involve
    > more than one architect/designer (who is also a skilled coder *), 2-3
    > developers, a great BA, and a good QA/QC person. I've found that a
    > skilled team this size outperforms a 20-30 person team easily, 9 times
    > out of 10.


    I have also found that small focused groups of up to 8 people can
    achieve amazing results when protected from outside interference.
    Whenever possible, we try to split up in teams about that size.
    Architecture and QA are usually orthogonal to that.

    > More specifically, what really is the complexity of introducing some
    > Clojure or Scala compared to requiring that your developers master new
    > Java APIs?


    It's not just the amount of complexity, its also where it lies - just
    development, or also build process, configuration management, deployment
    infrastructure setup (conventions for IDE settings etc.) If it were just
    learning a new language - most developers love to do that.

    I've seen considerably more project problems due to imperfect
    > understanding of JPA 1.x/2.x, or IO/NIO, or web services and WSDLs, or
    > RMI, or concurrency - all Java - than any problems caused by
    > implementing logic in a language better suited for it than Java.


    Quite true. If you don't know hat you're doing, you're bound to screw up
    in any language. With some things, however, it's not just API knowledge.
    Concurrency, for example, I believe to be an intrinsically difficult
    subject.

    > AHS
    >
    > * Not usually the case in my experience. I have no idea what process
    > anoints a majority of the "architects" out there, but it's not
    > programming skills.


    Do you know Simon Brown's work in progress "Software Architecture for
    Developers"? (https://leanpub.com/software-architecture-for-developers)
    Among other things it's about how coding is part of architecture, and
    what is "just enough" design. Entertaining read.

    -- Sebastian
    Sebastian, Jun 10, 2013
    #13
  14. Sebastian

    markspace Guest

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

    On 6/10/2013 10:43 AM, Sebastian wrote:

    > If you wish, just send me an email and I'll send you my code
    > privately as a point of departure. I don't wish to put it on
    > a public site, however.



    That's too bad, since Java 8 is new and we could use some examples how
    to implement algorithms with lambda.

    I assume you don't want to post the code because it's actually owned by
    your employer. Would you consider posting a scaled down example on a
    personal blog? Something that outlines how to solve this type of
    problem without actually revealing all the details? I found what you
    did post to be kind of hard to follow.

    Or if you can find some public code that does something similar, base
    your public post on that, and show where improvements and adaptations
    can be made.

    I've seen this done professionally. Neal Gafter, for example, didn't
    agree with all of the patent transfer stuff on the lambda dev list, so
    he often blogged his comments elsewhere and then provided a link and a
    summary to the list. It's just a way of maintain rights to material
    (publicly or privately) independent of an employer.
    markspace, Jun 10, 2013
    #14
  15. Sebastian

    Sebastian Guest

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

    Am 10.06.2013 22:18, schrieb markspace:
    > On 6/10/2013 10:43 AM, Sebastian wrote:
    >
    >> If you wish, just send me an email and I'll send you my code
    >> privately as a point of departure. I don't wish to put it on
    >> a public site, however.

    >
    >
    > That's too bad, since Java 8 is new and we could use some examples how
    > to implement algorithms with lambda.
    >

    [snip]

    I found what you did post to
    > be kind of hard to follow.
    >

    [snip]

    I have thought again, and will put something together on a blog. May
    take a day or two, I'll be back to post a link. It will still be hard
    to follow, though. Meanwhile, a good place to get started with the topic
    would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/

    -- Sebastian
    Sebastian, Jun 11, 2013
    #15
  16. Sebastian

    Stefan Ram Guest

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

    Sebastian <> writes:
    >would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/


    This says:

    »Capture of local variables is restricted to those that
    are effectively final. Lifting this restriction would
    present implementation difficulties«.

    Here's another story:

    »Guy Steele wrote:

    Actually, the prototype implementation *did* allow
    non-final variables to be referenced from within
    inner classes. There was an outcry from *users*,
    complaining that they did not want this!«

    http://madbean.com/2003/mb2003-49/
    Stefan Ram, Jun 12, 2013
    #16
  17. Sebastian

    Sebastian Guest

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

    Am 12.06.2013 01:17, schrieb Stefan Ram:
    > Sebastian<> writes:
    >> would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/

    >
    > This says:
    >
    > »Capture of local variables is restricted to those that
    > are effectively final. Lifting this restriction would
    > present implementation difficulties«.
    >
    > Here's another story:
    >
    > »Guy Steele wrote:
    >
    > Actually, the prototype implementation *did* allow
    > non-final variables to be referenced from within
    > inner classes. There was an outcry from *users*,
    > complaining that they did not want this!«
    >
    > http://madbean.com/2003/mb2003-49/
    >

    Brian Goetz gives concurrency issues as the reason in his "official"
    State of the lambda, section 7:

    "It is our intent to prohibit capture of mutable local variables. The
    reason is that idioms like this:

    int sum = 0;
    list.forEach(e -> { sum += e.size(); });

    are fundamentally serial; it is quite difficult to write lambda bodies
    like this that do not have race conditions. Unless we are willing to
    enforce—preferably at compile time—that such a function cannot escape
    its capturing thread, this feature may well cause more trouble than it
    solves."

    http://cr.openjdk.java.net/~briangoetz/lambda/lambda-state-4.html
    Sebastian, Jun 12, 2013
    #17
  18. Sebastian

    Sebastian Guest

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

    Am 11.06.2013 23:27, schrieb Sebastian:
    [snip]
    >
    > I have thought again, and will put something together on a blog. May
    > take a day or two, I'll be back to post a link. It will still be hard
    > to follow, though. Meanwhile, a good place to get started with the topic
    > would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/
    >
    > -- Sebastian


    I have written two blog entries about higher-order functions with Java 8
    lambda expressions. They can be found at

    http://sebastian-millies.blogspot.de/

    The second part is short and summarizes the content of this thread, plus
    it gives the complete coding example.

    The first part is more academic, perhaps suitable for use in
    introductory courses.

    I'd much appreciate any feedback. Either in the blog, or on this list.

    -- Sebastian
    Sebastian, Jun 12, 2013
    #18
  19. Sebastian

    Sebastian Guest

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

    Am 12.06.2013 21:05, schrieb markspace:
    > On 6/12/2013 5:37 AM, Sebastian wrote:
    >>
    >> I have written two blog entries about higher-order functions with Java 8
    >> lambda expressions. They can be found at
    >>
    >> http://sebastian-millies.blogspot.de/

    >
    >
    > Thanks for posting that, I'll try to check it out later. I also found
    > this blog, which looks like a good introduction to Java 8, lambdas in
    > particular.
    >
    > <http://www.techempower.com/blog/2013/03/26/everything-about-java-8/>
    >
    >
    >

    yes, that's good: pretty comprehensive, concise and clear. I've
    referenced it from my first blog entry.

    -- Sebastian
    Sebastian, Jun 12, 2013
    #19
  20. Sebastian

    markspace Guest

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

    On 6/12/2013 5:37 AM, Sebastian wrote:
    > Am 11.06.2013 23:27, schrieb Sebastian:
    > [snip]
    >>
    >> I have thought again, and will put something together on a blog. May
    >> take a day or two, I'll be back to post a link. It will still be hard
    >> to follow, though. Meanwhile, a good place to get started with the topic
    >> would be Maurice Naftalin's Lambda FAQ at http://www.lambdafaq.org/
    >>
    >> -- Sebastian

    >
    > I have written two blog entries about higher-order functions with Java 8
    > lambda expressions. They can be found at
    >
    > http://sebastian-millies.blogspot.de/


    So I had a chance to look at this a bit. Lambda are kind of cool. You
    can generate lists of number easily:

    static void test1() {
    Stream.iterate( 0, x -> x + 1 )
    ;
    }

    This actually runs, even though the list is infinite. Many streams are
    lazy, and don't evaluate unless asked for more. I guess the stream
    above initializes its values, but then never generates any numbers since
    it's never asked for any.

    Once you have a stream you can do cool things with it. You can limit
    the number of entries processed, for example, or filter them.

    You can also use "terminal functions" to do things other than pass more
    values back to a stream. Here forEach() is a terminal that I use to
    print the results of the stream.

    static void test2() {
    Stream.iterate( 0, x -> x + 1 )
    .limit(10)
    .filter( x -> (x % 2) == 1 )
    .forEach( x -> { System.out.println( x ); } )
    ;
    }

    This generates a stream, limits the total to 10, filters on the odd
    numbers (leaves only the odd numbers in the stream), and then prints the
    results.

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

    Here's the stream:

    Stream.iterate( 2, x -> x + 1 )
    .limit( 100 )
    .filter( sieve )
    .forEach( x -> { System.out.println( x ); } )
    ;

    Pretty much the same as before, except I've got a pre-defined variable
    "sieve" for a filter. What is this? Well it starts off as an anonymous
    class:

    Predicate<Integer> sieve = new Predicate<Integer>() {
    ....
    }

    So far so good. We need to override the test method for the Predicate:

    Predicate<Integer> sieve = new Predicate<Integer>() {
    @Override
    public boolean test( Integer candidate ) {
    ...
    }
    }

    OK, lets add the priority queue also:

    Predicate<Integer> sieve = new Predicate<Integer>() {
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    @Override
    public boolean test( Integer candidate ) {
    ...
    }
    }

    So far this looks like a regular old anonymous class. And it is. Now
    we just have to add the logic to remove primes. This doesn't require
    that we have access to other parts of the stream, because we're storing
    those values we care about in the priority queue. Whether that's good
    design or bad design I'm not sure, although Ms. O'Neil makes hash out of
    the naive algorithm in a simple Haskell implementation. So perhaps
    willy-nilly access to other parts of a stream isn't such a great idea.

    On the algorithm itself, if for example we find a prime at location 5,
    then we know it's prime because no previous factors (2, 3) are at this
    position. So we add 5 to the queue at position 10 (the next factor of
    5), and as we march up the line of integers, when we reach position 10,
    we see it has "5" attached to it. So we know 10 is not prime, and we
    take all the factors attached to 10, and put them back in the queue at
    their next position. In this example, the 5 goes back in the queue at
    position 15.

    The point here is that you actually need to store two numbers in the
    queue: a position, and the original factor to increase the current
    position by. That's why I need to create a Pair class below.

    The code isn't too bad. We just take a look at the queue, if nothing is
    there at our position, the number is prime.

    boolean prime = queue.peek().priority != candidate;

    If the value is prime, we just add a new Pair to the queue.

    if( prime ) {
    queue.add( new Pair( candidate*candidate, candidate ) );

    (An optimization Ms. O'Neil points out is that numbers can be added to
    the queue as the square of their initial values. I'll leave that bit as
    an exercise to the reader.)

    If the value was not prime, we have some previous values to process. I
    pull them out of the queue, add one more factor to their position, and
    put the back in the queue. Do this until there are no more factors at
    the current candidate prime location:

    while( queue.peek().priority == candidate )
    {
    Pair p = queue.poll();
    p.priority += p.factor;
    queue.add( p );
    }

    All this is somewhat complicated by the need to check for an empty queue
    and null values.

    Predicate<Integer> sieve = new Predicate<Integer>() {

    PriorityQueue<Pair> queue = new PriorityQueue<>();

    @Override
    public boolean test( Integer candidate ) {
    boolean prime = (queue.peek() != null ) ?
    queue.peek().priority != candidate : true ;
    if( prime ) {
    queue.add( new Pair( candidate*candidate, candidate ) );
    } else {
    while( queue.peek()!= null &&
    queue.peek().priority == candidate )
    {
    Pair p = queue.poll();
    p.priority += p.factor;
    queue.add( p );
    }
    }
    return prime;
    }

    };

    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.

    package sieve;

    import java.util.AbstractCollection;
    import java.util.Iterator;
    import java.util.PriorityQueue;
    import java.util.stream.Stream;
    import java.util.function.Predicate;

    /**
    * A simple lambda implementation of the sieve of
    * Eratosthenes.
    *
    * June 15, 2013
    *
    * @author Brenden Towey
    */
    public class Eratosthenes
    {

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


    private static class Pair implements Comparable<Pair>
    {
    public Pair( int priority, int factor )
    {
    this.priority = priority;
    this.factor = factor;
    }
    int priority;
    int factor;
    @Override
    public int compareTo( Pair pair ) {
    return Integer.compare( priority, pair.priority );
    }
    }


    static void test4() {

    Predicate<Integer> sieve = new Predicate<Integer>() {
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    @Override
    public boolean test( Integer candidate ) {
    boolean prime = (queue.peek() != null ) ?
    queue.peek().priority != candidate : true ;
    if( prime ) {
    queue.add( new Pair( candidate*candidate, candidate ) );
    } else {
    while( queue.peek()!= null &&
    queue.peek().priority == candidate )
    {
    Pair p = queue.poll();
    p.priority += p.factor;
    queue.add( p );
    }
    }
    return prime;
    }
    };

    Stream.iterate( 2, x -> x + 1 )
    .limit( 100 )
    .filter( sieve )
    .forEach( x -> { System.out.println( x ); } )
    ;
    }
    }
    markspace, Jun 15, 2013
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pawel Banys
    Replies:
    1
    Views:
    479
    Joe Smith
    Jul 8, 2004
  2. =?Utf-8?B?Sm9obiBIb3BwZXI=?=

    streams and querystrings

    =?Utf-8?B?Sm9obiBIb3BwZXI=?=, Jan 21, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    397
    =?Utf-8?B?Sm9obiBIb3BwZXI=?=
    Jan 21, 2005
  3. Steve Bergman
    Replies:
    15
    Views:
    485
    Klaas
    Nov 30, 2006
  4. Replies:
    4
    Views:
    2,327
  5. Daniel Baird

    golfing Eratosthenes

    Daniel Baird, Aug 2, 2006, in forum: Ruby
    Replies:
    13
    Views:
    224
    Chad Perrin
    Aug 2, 2006
Loading...

Share This Page