Pourquoi le générateur de permutation itérative est-il plus lent que récursif? - java, chaîne, récursivité, permutation

Je "compare deux fonctions à utiliser comme mongénérateur de permutation. Cette question concerne beaucoup de choses: le tableau interne des chaînes, les avantages et les inconvénients de l'utilisation de l'itération vs la récursivité pour ce problème, 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;
}

Je pense que ces deux algorithmes devraient être généralementégal, cependant la mise en œuvre récursive fonctionne bien jusqu'à n = 10, alors que permute1, la solution interactive, a une erreur de mémoire inutile à n = 8, où n est la longueur de la chaîne en entrée. Est-ce que le fait d’utiliser StringBuilder puis de convertir en chaînes est une mauvaise idée? Si oui, pourquoi? Je pensais que chaque fois que vous ajoutez une chaîne, elle en crée une nouvelle, ce qui serait mauvais, car java l’internerait, pas vrai? Donc, vous vous retrouveriez avec un tas de chaînes intermédiaires qui ne sont pas des permutations mais qui sont coincées dans la table interne.

MODIFIER:

J'ai remplacé StringBuilder avec String, quiSuppression de la nécessité d'utiliser StringBuilder.insert (). Cependant, je dois utiliser String.substring () pour construire les chaînes de permutation, ce qui n’est peut-être pas la meilleure façon de le faire, mais c’est empiriquement meilleur que StringBuilder.insert (). Je n’ai pas utilisé de tableau de caractères comme Alex Suo l'a suggéré car, comme ma méthode est supposée renvoyer une liste de chaînes, je devrais convertir ces tableaux de caractères en chaînes, ce qui induirait davantage de récupération de place sur les tableaux de caractères (la raison de OutOfMemoryError). , les problèmes OutOfMemoryError et de lenteur sont résolus.

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;
}

Réponses:

Premièrement, depuis que vous avez OutOfMemoryError, queCela me fait penser que vous avez beaucoup de GC en cours et, comme nous le savons tous, le GC est un tueur de performance. Comme la GC de la nouvelle génération est un monde immobile, les performances de cette dernière sont probablement bien pires.

En regardant votre code, si vous plongez dans le réelLors de l’implémentation de StringBuilder, vous avez pu constater que insert () est une opération très coûteuse impliquant System.arraycopy (), etc. et potentiellement expandCapacity (). Puisque vous ne mentionnez pas votre n pour la permutation, je suppose que le n <10 ne pose donc pas le problème - vous auriez une nouvelle allocation de mémoire car le tampon par défaut de StringBuilder est uniquement de la taille 16. StringBuilder est fondamentalement un tableau de caractères automatique mais ce n'est pas magique - quoi que vous fassiez en codant à partir de zéro, StringBuilder doit également le faire.

Cela dit, si vous voulez vraimentatteindre des performances maximales, puisque la longueur de votre tableau de chaînes est prédéfinie, pourquoi ne pas simplement utiliser un tableau de caractères avec length = String.length ()? C \ 'est probablement le meilleur en terme de performance.