Re: Easy exhaustive search with Java 8 Streams

[Jan Burse]

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
>

[j4n bur53]

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