J'ai écrit un arbre N-Ary ADT qui fonctionne bien. Cependant, je dois stocker sa sérialisation dans une variable une classe d'appel. par exemple.
public String printTree(AbstractTree<E> tree, StringBuilder buffer){
if (tree.isLeaf()){
return tree.getNodeName();
}else{
buffer.append(tree.getNodeName());
buffer.append("(");
int i = 0;
Iterator<AbstractTree<E>> child = tree.getChildren().iterator();
while (i < tree.getChildren().size() - 1){
buffer.append(printTree(child.next(), buffer));
buffer.append(", ");
i++;
}
buffer.append(printTree(child.next(), buffer));
buffer.append(")");
return buffer.toString();
}
}
6 Réponses :
Regardez à StringBuilder, n'utilisez pas de concaténation simple et transmettez le StringBuilder dans votre processus (ou faites-en un global).
Les concats de cordes comme celui-ci sont punisamment lents. Utilisez un StringBuilder.
@Override
public String toString(){
StringBuilder buffer = new StringBuilder();
printTree(this, buffer);
return buffer.toString();
}
public void printTree(AbstractTree<E> tree, StringBuilder buffer){
if (tree.isLeaf()){
buffer.append(tree.getNodeName());
} else {
buffer.append(tree.getNodeName());
buffer.append("(");
int i = 0;
Iterator<AbstractTree<E>> child = tree.getChildren().iterator();
while (i < tree.getChildren().size() - 1){
printTree(child.next(), buffer);
buffer.append(", ");
i++;
}
printTree(child.next(), buffer);
buffer.append(")");
}
}
J'ai suivi votre exemple, mais je reçois une OutofMemoryErrorror. J'ai mis le VM args à -xms2g -xmx2g, mais cela n'aide pas ...
Quel est le but de la chaîne renvoyée par la méthode?
Le but de la chaîne est de se brancher dans plusieurs algorithmes métriques de distance que je teste.
Osez-moi le dire, mais est-ce un exemple de la programmation itérative de manière importante de la programmation fonctionnelle?
N'utilisez pas la concaténation de la chaîne dans les boucles. Il n'a pas échoué.
Utilisez StringBuilder, cela ne fait pas de nouveaux objets tout le temps, comme la concaténation de chaîne .. }
C'est la réponse parfaite que je pense. La concaténation est bonne en dehors des boucles - en fait, la JVM l'optimise si bien qu'il est probablement plus rapide que d'utiliser l'une des alternatives, mais dans une boucle, la performance vient de mourir. Regardez le code source de chaîne si vous souhaitez voir des optimisations intéressantes.
@Bill K: performance meurt si mal dans une boucle au point que le coût total de la concaténation est O (N ^ 2) dans le pire des cas, non? Tout comme je l'ai dit dans ma réponse. Pouvez-vous regarder ma mise à jour?
J'admire la simplicité de votre réponse: parfait pour quelqu'un qui arrive ici de Google, comme moi. :)
Vous voudrez peut-être regarder
Le problème n'est pas une comparaison de chaînes, mais la concaténation de la chaîne; imho string.Intern () n'est pas efficace dans ce cas
Permettez-moi de dire la raison pour laquelle la concaténation de la chaîne est lente est que des cordes sont immuables. Cela signifie chaque fois que vous écrivez "+ =", une nouvelle chaîne est créée. Cela signifie que la façon dont vous construisez votre chaîne est dans le pire des cas, O (n 2 sup>). C'est parce que si vous avez + = 'Ed 1 Char à la fois, le coût de la construction d'une nouvelle chaîne serait de 2 + 3 + 4 + ... + N, qui est O (n 2 sup>). Utilisez StringBuilder comme des autres suggèrent (sur la stringbuffer plus lente, mais threadsafe). P> Je suppose que je devrais ajouter, StringBuilder vous donnera une heure (n) amortie, car cela fonctionne comme un vecteur derrière le scènes, puisqu'elle est mutable. Donc, accumulez votre chaîne là-bas, puis appellez Tostring (). P> StringBuilder builder = new StringBuilder();
builder.append("blah"); // append more as needed.
String text = builder.toString();
Corrigé en théorie, en réalité, vous devriez regarder la classe de cordes, certaines concatuations n'allouent pas réellement de nouvelles chaînes. La matrice interne utilisée pour stocker la chaîne peut être partagée entre deux chaînes de longueurs différentes - il peut donc être élargi et une nouvelle chaîne copiée derrière les deux chaînes existantes peut avoir les mêmes matrices de support avec des longueurs différentes. Le problème est que cela ne fonctionne qu'une seule fois - après que le drapeau "partagé" est défini, vous ne pouvez pas vraiment le refaire - donc dans les boucles que vous êtes complètement correct.
Alors pourquoi est-ce -1? J'ai aussi dit spécifiquement que c'est la pire performance des cas ... qui est définitivement correcte. Le pire des cas signifierait que les optimisations travaillent contre vous.
Mais ce n'est pas, quand dans une boucle. Peut-être que je devrais mettre à jour et clarifier.
Peut-être que la concaténation de chaîne n'est pas quadratique? Peut-être qu'il est linéaire O (n + m) où n = | str1 | et m = | str2 | ?
S'il vous plaît voir ma réponse clarifiée. C'est certainement linéaire pour une chose unique. Mais il est quadratique dans le pire des cas lorsque vous faites une série de concaténations.
@DFA: La raison pour laquelle il est quadratique est en raison du nombre de concaténations linéaires que vous faites. Si vous faites 1 caractères à la fois, vous obtenez (1 + 1) + (2 + 1) + (3 + 1) + ... + (N-1 + 1), qui est 2 + 3 + ... + n, qui est N * (N + 1) / 2 - 1, qui est O (n ^ 2).
Je suis un peu contrarié cette réponse est dans les négatifs ... Il n'y a vraiment rien de mal à ce que ce soit, et je pensais que ce serait bien de donner une explication quant à la raison pour laquelle les concaténations des boucles sont lentes (afin que l'OP puisse comprendre ), au lieu de simplement dire "Oh, ils sont lents, utilisez StringBuilder". Surtout maintenant que j'ai mis à jour et clarifié ...
Si un profileur Une corde est un remplacement de haute performance pour les chaînes. Le DataStructure, décrit en détail dans "Cordes: une alternative aux chaînes", fournit des performances asymptotiquement meilleures que la chaîne et Stringbuffer pour les modifications de chaîne courantes telles que la préparation, l'annexe, la suppression et l'insertion. Comme des cordes, des cordes sont immuables et donc bien adaptées à une utilisation dans une programmation multi-filetée.
Ne devinez pas. Obtenez-vous un profileur et mesurez-le.
Ok, vous mélangez et correspondez à d'anciennes et de nouvelles approches. J'ai mis à jour ma réponse pour vous montrer ce que je veux dire en totalité.