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 1 of 2  [1] 2  Next page →

#24289 — Java 8 Streams and Eratosthenes

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);
}

[toc] | [next] | [standalone]

#24291

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

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

#24300

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

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

#24302

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

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

#24313

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

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

#24347 — 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

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

#24348 — 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

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

#24350 — 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

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

#24354 — 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.

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

#24366 — 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

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

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

Am 12.06.2013 01:17, schrieb Stefan Ram:
> Sebastian<news@seyweiler.dyndns.org>  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

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

#24379 — 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

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

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

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

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

#24394 — 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

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

#24420 — 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 ); } )
               ;
    }
}

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

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

Am 16.06.2013 00:18, schrieb markspace:
> 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 )
> ;
> }
>
yes, I think its a good thing this is being added to Java. A real advance.

> 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.
yes, that's how it works. By the way, streams are not only lazy, but 
many tasks that work on streams can be parallelized by just calling the 
parallel() method on the stream. That's explicit but unobtrusive - all 
the concurrent stuff happens under the hood (based on the 
fork-join-framework of Java 7). I haven't yet looked at this in detail, 
though.

[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]
that's good to see. Thanks for sharing the code. It's nice having a real 
sieve of Eratosthenes now. (But I still like the simple formulation of 
the naive algorithm, just for its looks - although objectively it 
performs worse.)

I also like your step-by-step exposition.

Best Regards,
Sebastian

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

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

On 06/15/2013 07:18 PM, markspace wrote:
> On 6/12/2013 5:37 AM, Sebastian wrote:
[ SNIP ]

Good stuff, guys, both of you. This is the kind of Java thread that 
really appeals to me. You both got me motivated to get the latest Java 8 
snapshot for Linux and start messing around with this stuff.

I tend to be a bit of a snob because of having used Haskell, Scala, 
OCaml, LISP/Lisp, Scheme etc extensively, and F# most recently. I like 
the cleaner forms where you can one-line something that even in Java 8 
may take a page of code.

But it occurred to me, based on something Sebastian said, that if Java's 
all you've got, and many workplaces do narrowly dictate that, then it 
helps if the language and APIs have got these capabilities.

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

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

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

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));
     }
}

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

#24293

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

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

#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

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web