Java 8 String Unique Permutations in Parallel

Question

Is there a better way to do this Java 8 String Unique Permutations in Parallel

package com.bos;

import java.util.Date;
import java.util.Set;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.stream.IntStream;

public class StringPermutation {
    private static Set<String> set = new ConcurrentSkipListSet<String>();

    public static void permutation(String str) {
        permutation("", str);
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            set.add(prefix);
        } else {
            IntStream.range(0, n).parallel()
                    .forEach(i -> permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));
        }
    }

    public static void main(String[] args) {
        Date startDate = new Date();
        long startTime = System.nanoTime();
        System.out.println("Started at " + startDate);
        permutation("ferrao");
        set.stream().forEach(System.out::println);
        Date endDate = new Date();
        long totalTime = System.nanoTime() - startTime;
        System.out.println("Ended at " + endDate + " total time=" + totalTime + " nanosec");

    }
}

Answer 1

The presented way is not a functional solution. It uses streams but it relies on forEach, which is the imperative way of using a Stream.

To make it better, we need to think about what we really want to do. We want to build all the permutations of the characters in a String. That means we need to have a method permutations(String) that will return all the permutations. Using Java 8, we can return a Stream<String> which will corresponds to the Stream of all the permutations.

To build those permutations, we can have a recursive algorithm:

• If the String is empty, there are no characters, so the only result is a Stream that contains the empty String. This is the base case.
• If the String is non-empty:
  • we remove the first character, build all the permutations without it and then prepend the first character to all the results.
  • then we remove the second character, build all the permutations without it and then prepend the second character to all the results.
  • etc. until we hit the last character.

Using Java 8, this is an implementation:

public static Stream<String> permutations(String str) {
    if (str.isEmpty()) {
        return Stream.of("");
    }
    return IntStream.range(0, str.length())
                .boxed()
                .flatMap(i ->
                  permutations(str.substring(0, i) + str.substring(i+1)).map(t -> str.charAt(i) + t)
                );
}

The base-case is handled by the if: when the String is empty, we return Stream.of(""): a Stream that contains only the empty String/

The main part is after: we create an IntStream over the indexes of the String. (Since there are unfortunately no flatMapToObj operation, we need to box each int into an Integer.) Then that's where the magic happens: for each index, we recurse by building all the permutations again, leaving the index i, and each of the result is mapped to prepend the character at index i. Since this recursive call returns a Stream<String>, this result is flat mapped (with flatMap) to have a single Stream.

With this utility method, your code is then just

permutations("ferrao").forEach(System.out::println);

That brings also a big advantage: the method is returning a Stream<String>, that is to say, the method does not actually perform the calculation. It is then up-to the caller to decide when to do it, if they want it to happen in parallel or not, and especially what the end container will be (a List, a Set, no container at all with just post-processing afterwards).

For example, to have it performed in parallel, you just need to do

permutations("ferrao").parallel().forEach(System.out::println);

Answer 2

I cannot help you with the actual permutation algorithm, yet you could make your snippet a little bit more object-oriented.

Ideally, you create StringPermutation giving the source string as a parameter; StringPermutation generates all unique permutations of the input string and stores them in a Set; the user may ask for a copy of that set.

All in all, you might come up with something like this:

public class StringPermutation {
    private Set<String> set = new ConcurrentSkipListSet<>();

    public StringPermutation(String str) {
        permutation("", str);
    }

    public Set<String> getStringSet() {
        return new LinkedHashSet<>(set);
    }

    private void permutation(String prefix, String str) {
        int n = str.length();

        if (n == 0) {
            set.add(prefix);
        } else {
            IntStream.range(0, n)
//                     .parallel()
                     .forEach(i -> permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));
        }
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        StringPermutation sp = new StringPermutation("lxferrao");
        long totalTime = System.nanoTime() - startTime;

        sp.getStringSet().stream().forEach(System.out::println);
        System.out.println("Total time = " + totalTime / 1e6 + " milliseconds.");
    }
}

Also, parallel() does not seem to speed up anything (try it).

Answer 3

As for time estimation, it's unclear what are you trying to measure here. Your time measurement code includes both permutations and printing. Printing is very slow and may greatly depend on the output device (/dev/null, console, file, IDE window). So the measured time is actually garbage. Suppose that we measure only set creation:

long startTime = System.nanoTime();
permutation("ferrao");
long totalTime = System.nanoTime() - startTime;

In this case you measure the time of single launch. Stream performance differs greatly between first launch and consequent launches. There's significant constant delay for initial class loading, lambda runtime representation generation, initialization of common thread pool and so on. Also initially the code is interpreted, then C1-compiled and only after many launches it reaches full speed after C2-compilation. If we simply put the body of the main() method into the loop (recreating the set before each iteration) and measure time several times, we will notice that the results differ significantly (only "Ended" lines):

Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=97973625 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=3628849 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=2533010 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=3297117 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=2310532 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=2422764 nanosec
...
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=293989 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=525075 nanosec
Ended at Mon Feb 15 22:55:17 NOVT 2016 total time=573743 nanosec

So you may see that first launch is about 200 times slower than launch#100. So when you measure performance you should decide what do you actually want to measure: the asymptotical steady state performance? First launch performance? Average on first 10 launches? Refer here for further reading.