A propos de String et StringBuilder
Comparaison des méthodes
d'intersection des ensembles
de lettres
dernière mise à jour 19/01/2022
Philippe Genoud
[Link]@[Link]
©
© Philippe
Philippe GENOUD
GENOUD UGA
UJF Octobre
Janvier 2022
2010 1
Modélisation d'un ensemble de lettres
a b c d e f g h i j k l m n o p q r s t u v w x y z
Représentation d'un ensemble de
lettres par un tableau de booléens
a b c d e f g h i j k l m n o p q r s t u v w x y z
{'c','e','h','k','u','x'} F F T F T F F T F F T F F F F F F F F F T F F T F F
Modélisation Objet (Java) d'un ensemble de lettres
public class EnsembleDeLettres {
private boolean[] present = new boolean[26]; un ensemble est un objet dont l'état est représenté par
un tableau de booléens
public EnsembleDeLettres(String s) {
...
}
...
}
Utilisation de la classe EnsembleDeLettres
EnsembleDeLettres e1 = new EnsembleDeLettres("cehkux");
EnsembleDeLettres e2 = new EnsembleDeLettres("acehkmuxz");
e1 present
e2 present
© Philippe GENOUD UGA Janvier 2022 2
A propos de String
Calculer intersection de deux ensembles de lettres [Link]
1ère idée utiliser méthode concat de la classe String
public EnsembleDeLettres intersection1(EnsembleDeLettres e) {
String inter = "";
for (int i = 0; i < [Link]; i++) {
// l'element i est dans l'intersection si il est dans this ET dans e
if ([Link][i] && [Link][i]) {
[Link](toChar(i));
}
}
return new EnsembleDeLettres(inter);
}
EnsembleDeLettres e1 = new EnsembleDeLettres("abcdefghijklmnopqrstuvwxyz");
EnsembleDeLettres e2 = new EnsembleDeLettres("abcdefghijklmnopqrstuvwxyz");
EnsembleDeLettres e3 = e1.intersection1(e2);
[Link]("e3 : ", e3); e3 : {} Donne l'ensemble vide. Pourquoi ?
© Philippe GENOUD UGA Janvier 2022 3
A propos de String
public EnsembleDeLettres intersection1(EnsembleDeLettres e) {
1 String inter = "";
for (int i = 0; i < [Link]; i++) {
// l'element i est dans l'intersection si il est dans this ET dans e
if ([Link][i] && [Link][i]) {
[Link](toChar(i)); toChar renvoie une
} 3 variable de type primitif
2
} char, mais concat
return new EnsembleDeLettres(inter); prend en paramètre un
} String conversion
vers un objet
Les String sont des objets 1
immuables (immutable) inter "" "a" 2
concat
3
concat ne modifie pas la chaîne inter "a"
concat "b" 2'
mais crée et retourne un nouvel objet
3'
"b"
…
© Philippe GENOUD UGA Janvier 2022 4
A propos de String
public EnsembleDeLettres intersection1(EnsembleDeLettres e) {
String inter = "";
1 for (int i = 0; i < [Link]; i++) {
// l'element i est dans l'intersection si il est dans this ET dans e
if ([Link][i] && [Link][i]) {
inter = [Link](toChar(i)); // inter = inter + toChar(i);
} 4 3 2
}
return new EnsembleDeLettres(inter);
}
1
inter "" "a" 2
concat
4 3
"a"
concat "b" 2'
4' 3'
"ab"
concat
"c"
si e1 et e2 contiennent les 26 lettres de l'alphabet,
e1.intersection1(e2) provoque la création de 53 objets String "abc"
…
© Philippe GENOUD UGA Janvier 2022 5
Performances
public EnsembleDeLettres intersection1(EnsembleDeLettres e) {
String inter = "";
for (int i = 0; i < [Link]; i++) {
// l'élément i est dans l'interection si il est dans this ET dans e
if ([Link][i] && [Link][i]) { La création d'objets
inter += toChar(i));
} coûte cher.
}
return new EnsembleDeLettres(inter);
}
public EnsembleDeLettres intersection3(EnsembleDeLettres e) {
EnsembleDeLettres res = new EnsembleDeLettres(); // res == ens vide
for (int i = 0; i < [Link]; i++) {
// l'element i est dans l'interection si il est dans this ET dans e
[Link][i] = [Link][i] && [Link][i];
}
return res;
}
e1 = new EnsembleDeLettres(
"abcdefghijklmnopqrstuvwxyz");
e2 = new EnsembleDeLettres(
"abcdefghijklmnopqrstuvwxyz");
e3 = e1.intersection1(e2);
Java 1.8.0_192
© Philippe GENOUD UGA Janvier 2022 6
StringBuilder vs. String
String n’est pas seule classe pour manipuler des chaînes dans l’API Java
© Philippe GENOUD UGA Janvier 2022 7
StringBuilder vs. String
Utilisationd’un objet StringBuilder au lieu d’objets String dans le calcul de
l’intersection de deux ensembles
public EnsembleDeLettres intersection2(EnsembleDeLettres e) {
String inter = ""; 1 StringBuilder inter = new StringBuilder();
for (int i = 0; i < [Link]; i++) {
// l'element i est dans l'interection si il est dans this ET dans e
if ([Link][i] && [Link][i]) {
inter += toChar(i); [Link](toChar(i));
} 3 2
}
return new EnsembleDeLettres(inter);
} return new EnsembleDeLettres([Link]());
Surcharge de append
1
inter "ab"
"a"
""
"abc" 'a' 2
append
3
append 'b' 2'
Variable de type primitif
3'
append 'c’
…
© Philippe GENOUD UGA Janvier 2022 8
Performances String/StringBuilder
Java 1.8.0_192
© Philippe GENOUD UGA Janvier 2022 9