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

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

Easy exhaustive search with Java 8 Streams

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

Contents

  Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-27 20:32 +0200
    Re: Easy exhaustive search with Java 8 Streams Jan Burse <janburse@fastmail.fm> - 2015-04-28 12:35 +0200
      Re: Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-29 11:12 +0200
        Re: Easy exhaustive search with Java 8 Streams j4n bur53 <janburse@fastmail.fm> - 2015-04-30 09:02 +0200
    Re: Easy exhaustive search with Java 8 Streams Sebastian <news@seyweiler.dyndns.org> - 2015-04-29 09:45 +0200

#31616 — Easy exhaustive search with Java 8 Streams

Hello there,

I have just been reading this post by Mark Dominus on Haskell:
http://blog.plover.com/prog/haskell/monad-search.html

Mark discusses how the Haskell list monad can be used to hide some of 
the glue code involved in doing exhaustive searches. Java 8 Streams, 
which are somewhat similar to Haskell lists in also being monadic, lend 
themselves to the same style of coding. The example is the well-known 
crypt-arithmetics puzzle of SEND + MORE = MONEY.

I quite liked Mark's post, and so I have ported his code to Java 8, 
which I'd like to share:

          List<Integer> DIGITS =
             unmodifiableList(asList(0,1,2,3,4,5,6,7,8,9));

          List<String> solutions =
             remove(DIGITS, 0).stream().flatMap( s ->
             remove(DIGITS, s).stream().flatMap( e ->
             remove(DIGITS, s, e).stream().flatMap( n ->
             remove(DIGITS, s, e, n).stream().flatMap( d ->
             remove(DIGITS, 0, s, e, n, d).stream().flatMap( m ->
             remove(DIGITS, s, e, n, d, m).stream().flatMap( o ->
             remove(DIGITS, s, e, n, d, m, o).stream().flatMap( r ->
             remove(DIGITS, s, e, n, d, m, o, r).stream().flatMap( y ->
                 { int send = toNumber(s, e, n, d);
                   int more = toNumber(m, o, r, e);
                   int money = toNumber(m, o, n, e, y);
                   return send + more == money
                      ? Stream.of(solution(send, more, money))
                      : Stream.empty();
                 }
             ))))))))
             .map(Object::toString)
             .collect(toList());

          System.out.println(solutions);

The minor optimization of not unncecessarily recomputing "send" and 
"more" is left out for the sake of readability. The methods remove() - 
which implements list difference - toNumber(), and solution() have 
simple implementations. Of these, toNumber() is again a lot like the 
corresponding Haskell code:

          Stream.of(digits).reduce((x,y) -> 10*x + y).get();

solution() here returns a String because Java does not have tuples. The 
call to map() is there to make the compiler happy, but is functionally 
the identity.

Too bad that in Java one must have the nested method calls, but the 
formatting goes some way to hide this. All in all, I think this is quite 
nice.

-- Sebastian

[toc] | [next] | [standalone]

#31619

Hi,

How fast is this? Any figures?

Bye

Sebastian schrieb:
> Hello there,
>
> I have just been reading this post by Mark Dominus on Haskell:
> http://blog.plover.com/prog/haskell/monad-search.html
>
> Mark discusses how the Haskell list monad can be used to hide some of
> the glue code involved in doing exhaustive searches. Java 8 Streams,
> which are somewhat similar to Haskell lists in also being monadic, lend
> themselves to the same style of coding. The example is the well-known
> crypt-arithmetics puzzle of SEND + MORE = MONEY.
>
> I quite liked Mark's post, and so I have ported his code to Java 8,
> which I'd like to share:
>
>           List<Integer> DIGITS =
>              unmodifiableList(asList(0,1,2,3,4,5,6,7,8,9));
>
>           List<String> solutions =
>              remove(DIGITS, 0).stream().flatMap( s ->
>              remove(DIGITS, s).stream().flatMap( e ->
>              remove(DIGITS, s, e).stream().flatMap( n ->
>              remove(DIGITS, s, e, n).stream().flatMap( d ->
>              remove(DIGITS, 0, s, e, n, d).stream().flatMap( m ->
>              remove(DIGITS, s, e, n, d, m).stream().flatMap( o ->
>              remove(DIGITS, s, e, n, d, m, o).stream().flatMap( r ->
>              remove(DIGITS, s, e, n, d, m, o, r).stream().flatMap( y ->
>                  { int send = toNumber(s, e, n, d);
>                    int more = toNumber(m, o, r, e);
>                    int money = toNumber(m, o, n, e, y);
>                    return send + more == money
>                       ? Stream.of(solution(send, more, money))
>                       : Stream.empty();
>                  }
>              ))))))))
>              .map(Object::toString)
>              .collect(toList());
>
>           System.out.println(solutions);
>
> The minor optimization of not unncecessarily recomputing "send" and
> "more" is left out for the sake of readability. The methods remove() -
> which implements list difference - toNumber(), and solution() have
> simple implementations. Of these, toNumber() is again a lot like the
> corresponding Haskell code:
>
>           Stream.of(digits).reduce((x,y) -> 10*x + y).get();
>
> solution() here returns a String because Java does not have tuples. The
> call to map() is there to make the compiler happy, but is functionally
> the identity.
>
> Too bad that in Java one must have the nested method calls, but the
> formatting goes some way to hide this. All in all, I think this is quite
> nice.
>
> -- Sebastian
>

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

#31624

Am 28.04.2015 12:35, schrieb Jan Burse:
> Hi,
>
> How fast is this? Any figures?
>
> Bye
>

I did a simple micro-benchmark with JMH 1.9.1 (available from Maven 
Central) on my laptop computer, which is a quad-core machine with an 
Intel i7 processor.

Here are the measurement parameters:

# JMH 1.9.1 (released 5 days ago)
# VM invoker: C:\Program Files\Java\jdk1.8.0_25\jre\bin\java.exe
# VM options: -Dfile.encoding=UTF-8
# Warmup: 5 iterations, 1 s each
# Measurement: 25 iterations, 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Average time, time/op

I measured the flatMap solution against the equivalent formulation with 
eight nested for-loops. The flatMap solution is about half as fast. 
Here's a representative measurement:


Benchmark                        Mode  Cnt    Score   Error  Units
measureFlatMpSearchPerformance   avgt   25  662.377 ± 3.747  ms/op
measureForLoopSearchPerformance  avgt   25  316.105 ± 3.823  ms/op


The nice thing abbout Streams is they are so easily parallelizable.
Just throw in a ".parallel()" in the first line like this:

    remove(DIGITS, 0).stream().parallel().flatMap( s ->

leaving everything else unchanged, and the (parallel) flatMap version 
becomes twice as fast as the (serial) for-loop version:


Benchmark                        Mode  Cnt    Score   Error  Units
measureFlatMpSearchPerformance   avgt   25  168.278 ± 1.700  ms/op
measureForLoopSearchPerformance  avgt   25  315.806 ± 2.878  ms/op


The effectiveness of parallelization of course depends on the 
problem-specific properties of your search space.

-- Sebastian

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

#31626

Thank you for sharing.

Sebastian schrieb:
> Am 28.04.2015 12:35, schrieb Jan Burse:
>> Hi,
>>
>> How fast is this? Any figures?
>>
>> Bye
>>
>
> I did a simple micro-benchmark with JMH 1.9.1 (available from Maven
> Central) on my laptop computer, which is a quad-core machine with an
> Intel i7 processor.
>
> Here are the measurement parameters:
>
> # JMH 1.9.1 (released 5 days ago)
> # VM invoker: C:\Program Files\Java\jdk1.8.0_25\jre\bin\java.exe
> # VM options: -Dfile.encoding=UTF-8
> # Warmup: 5 iterations, 1 s each
> # Measurement: 25 iterations, 1 s each
> # Timeout: 10 min per iteration
> # Threads: 1 thread, will synchronize iterations
> # Benchmark mode: Average time, time/op
>
> I measured the flatMap solution against the equivalent formulation with
> eight nested for-loops. The flatMap solution is about half as fast.
> Here's a representative measurement:
>
>
> Benchmark                        Mode  Cnt    Score   Error  Units
> measureFlatMpSearchPerformance   avgt   25  662.377 ± 3.747  ms/op
> measureForLoopSearchPerformance  avgt   25  316.105 ± 3.823  ms/op
>
>
> The nice thing abbout Streams is they are so easily parallelizable.
> Just throw in a ".parallel()" in the first line like this:
>
>     remove(DIGITS, 0).stream().parallel().flatMap( s ->
>
> leaving everything else unchanged, and the (parallel) flatMap version
> becomes twice as fast as the (serial) for-loop version:
>
>
> Benchmark                        Mode  Cnt    Score   Error  Units
> measureFlatMpSearchPerformance   avgt   25  168.278 ± 1.700  ms/op
> measureForLoopSearchPerformance  avgt   25  315.806 ± 2.878  ms/op
>
>
> The effectiveness of parallelization of course depends on the
> problem-specific properties of your search space.
>
> -- Sebastian

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

#31621

Am 28.04.2015 23:01, schrieb Stefan Ram:
> Sebastian <news@seyweiler.dyndns.org> writes:
>> remove(DIGITS, s, e, n, d, m, o, r).stream().flatMap( y ->
>
> The program above has a hardcoded solution for a single specific
> fixed puzzle. So, for the next puzzle, it has to be written anew?
> This is »easy«?
>
> I like generalized solutions:
>

Quite so. But I believe you misunderstood the aim of my post. I simply
wanted to point out a particular use of a monadic interface in Java. The 
particular example was completely irrelevant to that point. (What was 
relevant, however, was finding ALL solutions, not just one.)

-- Sebastian

[toc] | [prev] | [standalone]

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

csiph-web