CODEWITHSUNDEEP
javastringrecursionpermutation
Calicoder
Calicoder

Reputation: 1452

Why is iterative permutation generator slower than recursive?

I'm comparing two functions for use as my permutation generator. This question is about alot of things: the string intern table, the pros and cons of using iteration vs recursion for this problem, etc...

public static List<String> permute1(String input) {
    LinkedList<StringBuilder> permutations = new LinkedList<StringBuilder>();
    permutations.add(new StringBuilder(""+input.charAt(0)));

    for(int i = 1; i < input.length(); i++) {
        char c = input.charAt(i);
        int size = permutations.size();
        for(int k = 0; k < size ; k++) {
            StringBuilder permutation = permutations.removeFirst(),
                    next;
            for(int j = 0; j < permutation.length(); j++) {
                    next = new StringBuilder();
                    for(int b = 0; b < permutation.length(); next.append(permutation.charAt(b++)));
                    next.insert(j, c);
                    permutations.addLast(next);
            }
            permutation.append(c);
            permutations.addLast(permutation);
        }
    }
    List<String> formattedPermutations = new LinkedList<String>();
    for(int i = 0; i < permutations.size(); formattedPermutations.add(permutations.get(i++).toString()));
    return formattedPermutations;
}

public static List<String> permute2(String str) { 
    return permute2("", str); 
}

private static List<String> permute2(String prefix, String str) {
    int n = str.length();
    List<String> permutations = new LinkedList<String>();
    if (n == 0) permutations.add(prefix);
    else 
        for (int i = 0; i < n; i++) 
            permutations.addAll(permute2(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)));
    return permutations;
}

I think these two algorithms should be generally equal, however the recursive implementation does well up to n=10, whereas permute1, the interative solution, has an outofmemoryerror at n=8, where n is the input string length. Is the fact that I'm using StringBuilder and then converting to Strings a bad idea? If so, why? I thought whenever you add to a string it creates a new one, which would be bad because then java would intern it, right? So you'd end up with a bunch of intermediate strings that aren't permutations but which are stuck in the intern table.

EDIT:

I replaced StringBuilder with String, which removed the need to use StringBuilder.insert(). However, I do have to use String.substring() to build up the permutation strings, which may not be the best way to do it, but it's empirically better than StringBuilder.insert(). I did not use a char array as Alex Suo suggested because since my method is supposed to return a list of strings, I would have to convert those char arrays into strings which would induce more garbage collection on the char arrays (the reason for the OutOfMemoryError). So with this in place, both the OutOfMemoryError and slowness problems are resolved.

public static List<String> permute3(String input) {
        LinkedList<String> permutations = new LinkedList<String>();
        permutations.add(""+input.charAt(0));
        for(int i = 1; i < input.length(); i++) {
            char c = input.charAt(i);
            int size = permutations.size();
            for(int k = 0; k < size ; k++) {
                String permutation = permutations.removeFirst(),
                        next;
                for(int j = 0; j < permutation.length(); j++) {
                        next = permutation.substring(0, j + 1) + c + permutation.substring(j + 1, permutation.length());
                        permutations.addLast(next);
                }
                permutations.addLast(permutation + c);
            }
        }
        return permutations;
    }

Upvotes: 0

Views: 596

Answers (1)

Alex Suo
Alex Suo

Reputation: 3119

Firstly, since you got OutOfMemoryError, that hints me you have a lot of GC going on and as we all know, GC is a performance killer. As young-gen GC is stop-the-world, you probably get a lot worse performance by suffering from GCs.

Looking at your code, if you dive into the actual implementation of StringBuilder, you could see that insert() is a very expensive operation involving System.arraycopy() etc and potentially expandCapacity(). Since you don't mention your n for permutation I'd assume the n<10 so you won't have the problem here - you would have memory re-allocation since default buffer of StringBuilder is of size 16 only. StringBuilder is basically an auto char array but it's not magic - whatever you need to do by coding up from scratch, StringBuilder also needs to do it.

Having said the above, if you really want to achieve maximum performance, since the length of your string array is pre-defined, why not just use a char array with length = String.length() ? That's probably the best in term of performance.

Upvotes: 1

Related Questions