Code Puzzle: Anagram Detector with Lambdas in Java 8

A while ago we looked at some different approaches to detect anagrams given two strings. In our last detector we constructed a frequency map to determine the character counts of the input strings. This was much more efficient than earlier attempts in that it allowed us to construct a map with a single scan per string.

With Java 8 coming out early next year, now is a good time to revisit this problem with Lambdas! Let’s rework the frequency map approach with Java 8.

The first thing to notice is that using a HashMap carries overhead of checking whether a value has already been mapped or not. This entails calculations with hashcode() and equals(). While not expensive, we can do better. At the cost of more space initially, we can use an array to represent the frequency map. The array index can be the integer value of a character, and the value in the array at that index can be the count for that character. This allows us to directly map a character without any calculation, and to always do a simple increment as long as the array is initialized to all zeros.

Now for the lambda code! Here are the relevant points.

  • String.chars() returns a Stream. The Stream object is a central concept in JDK8 Lambdas
  • Stream.collect() is a reduce operation that mutates the initial value. It’s kind of un-functional to mutate function arguments (causing side effects), but this saves us the overhead of re-creating and combining maps.
  • The initial value is a zeroed-out array, and it is modified by the accumulator
  • The resulting code is actually concise enough that we don’t need a createFrequencyMap() method like we did before.

import java.util.Arrays;
import java.util.HashMap;
import java.util.function.BiConsumer;
import java.util.function.ObjIntConsumer;
import java.util.function.Supplier;
public class LambdaDetector implements AnagramDetector {

  private static final int MAX_VALUE = 65280;

  @Override
  public boolean isAnagram(String input1, String input2) {

     // null and length checks omitted for brevity
     Supplier<Long[]> start = () -> { Long[] a = new Long[MAX_VALUE]; Arrays.fill(a, 0L); return a; };
     ObjIntConsumer<Long[]> accumulator = (map, number) -> { map[number]++; };
     BiConsumer<Long[],Long[]> combiner = (map1, map2) -> {  };

     return Arrays.equals( input1.chars().collect(start, accumulate, combine),
                           input2.chars().collect(start, accumulate, combine));

  }

}

There is a lot to JDK8 Lambdas, this sample barely scratches the surface. Next time we can look at what lambdas bring to the table, my favorites would be easy parallelism and lazy operations. Exciting times are ahead!

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s