The example used in the post I have quoted is the well-known crypt-arithmetics puzzle in which you are asked to find all possible ways of mapping the letters
S
, E
, N
, D
, M
,
O
, R
, Y
to distinct digits 0 through 9 (where we may assume that S
is not 0) so that the following comes out true:S E N D + M O R E --------- M O N E Y
Here's my Java 8 port of Mark's Haskell example.
public class SendMoreMoney { static final List<Integer> DIGITS = unmodifiableList(asList(0,1,2,3,4,5,6,7,8,9)); public static void main(String[] args) { 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, 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(); } )))))))) .collect(toList()); System.out.println(solutions); } static String solution(int send, int more, int money) { return "(" + send + "," + more + "," + money + ")"; } static final int toNumber(Integer... digits) { assert digits.length > 0; return Stream.of(digits).reduce((x,y) -> 10*x + y).get(); } static final List<Integer> remove(List<Integer> xs, Integer... ys) { // this naive implementation is O(n^2). List<Integer> zs = new ArrayList<>(xs); zs.removeAll(asList(ys)); return zs; } }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. Method solution() here returns a String because Java does not have tuples.
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.
But how fast is it? 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 forEach-loops and an external accumulator variable. The flatMap solution is about half as fast. Here's a representative measurement:
Benchmark Mode Cnt Score Error Units
measureFlatMapSearchPerformance 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
measureFlatMapSearchPerformance avgt 25 168.278 ± 1.700 ms/op
measureForLoopSearchPerformance avgt 25 315.806 ± 2.878 ms/op
No comments:
Post a Comment