Préférer String ou tableau de char

Bonjour

J'ai une question d'ordre assez technique.
Je souhaiterai développer une application qui réalise beaucoup d'opérations sur des chaines de caractères. Cependant, je me pose la question de l'utilité de l'utilisation de String, car je veux seulement faire des comparaisons caractères à caractères.

Faut-il mieux utiliser des String :
str.charAt(i) != str.charAt(j)
... ou alors des tableaux de char :
str[i] != str[j]
?

Merci

Pierre

accéder à un index du tableau est plus rapide que d'appeler une méthode qui elle même accèdera à un index. A toi de faire l'évaluation entre la rapidité et la facilité de gérer le code.

Il a raison.
Cependant si tes opérations devaient modifier ces chaines, je pencherais plus vers les StringBuffer et StringBuilder.

Citation:

---

Envoyé par tchize_

accéder à un index du tableau est plus rapide que d'appeler une méthode qui elle même accèdera à un index. A toi de faire l'évaluation entre la rapidité et la facilité de gérer le code.

---

Très bien.
Je pense notamment qu'une allocation d'un tableau de caractère doit être plus rapide qu'une allocation d'une instance de String.
J'ai une question subsidiaire, toujours en quête de rapidité. Je ne souhaite pas modifier ces chaines de caractères dans mes fonctions. Le "final" pour le passage de l'argument de cette chaine dans une fonction est-il source de pertes de rapidité ? (Je ne connais pas les mécanismes sombre de Java, mais la JVM doit faire une copie de cette variable en cas d'un "final"...)

Merci

Pierre

java ne passe jamais de paramètres par copie, sauf les type de bases (int, double, float, char, boolean, long). Donc, dans le cas de ton tableau, ce sera le tableau de base qui sera passé. Par contre, je pense, le final n'empechera pas de modifier le contenu du tableau, ca empechera juste de créer un nouveau tableau sur le même nom de variable.

Citation:

---

Envoyé par tchize_

java ne passe jamais de paramètres par copie, sauf les type de bases (int, double, float, char, boolean, long). Donc, dans le cas de ton tableau, ce sera le tableau de base qui sera passé. Par contre, je pense, le final n'empechera pas de modifier le contenu du tableau, ca empechera juste de créer un nouveau tableau sur le même nom de variable.

---

Quand tu dis types de base (...char...), est-ce aussi le cas pour des tableaux de types de base ? (en particulier, char[])...

Merci

les tableau ne sont pas des type de base, donc ton tableau ne sera pas copié. Ce sera la référence au tableau qui sera passée.

Citation:

---

Envoyé par tchize_

java ne passe jamais de paramètres par copie, sauf les type de bases (int, double, float, char, boolean, long). Donc, dans le cas de ton tableau, ce sera le tableau de base qui sera passé. Par contre, je pense, le final n'empechera pas de modifier le contenu du tableau, ca empechera juste de créer un nouveau tableau sur le même nom de variable.

---

Citation:

---

Envoyé par tchize_

les tableau ne sont pas des type de base, donc ton tableau ne sera pas copié. Ce sera la référence au tableau qui sera passée.

---

:nono: java passe toujours tous les paramètres par copie.
Dans le cas de type primitifs il s'agit d'une copie de la valeur, dans le cas d'un objet ou d'un tableau il s'agit d'une copie de la référence vers ledit objet/tableau.
Bien sûr cette nouvelle référence pointe vers le même objet/tableau allouer dans le tas et donc une modification d'un attribut/élément de l'objet/tableau se retrouvera après l'appel de la méthode. Cependant si tu modifies la reférence elle même (param = new Object(); ) l'originale n'est pas modifiée ;).

exact, merci de m'avoir corrigé ;)

Salut,


Pour revenir au sujet : ForgetTheNorm > Quel intérêt y-a-t'il à utiliser des tableaux de char ? Quels sont les opérations que tu dois faire sur ces chaines ?

Parce que le couple String/StringBuilder te permet déjà de faire beaucoup de chose...

a++

En plus si c'est une question de vitesse, suivant comment ce n'est peut être pas la peine de rendre son code beaucoup moins lisible et agréable juste pour gagner 2sec sur un traitement d'une minute, ou 200ms sur un traitement de 5 secondes.

Les classes Stringbuffer / builder de java sont passablement au point question performance et passent d'une méthode à une autre sans duplication.

préférer stringbuilder à stringbuffer quand même :D Sauf si synchro multi threads nécessaire.

Merci pour vos réponses.

Le soucis est que j'ai un code qui tourne sans problème mais qui résiste mal à l'échelle. Tout le code est basé sur une fonction qui compare une chaine à une autre, pour l'instant compare(String, String). Le soucis est que la majorité du temps de calcul est utilisé par cette fonction, alors que je ne fais que des comparaisons de String.charAt(i) == String.charAt(j).

D'où ma question : est-ce que c'est plus rapide d'avoir une fonction compare(char[], char[]) et de remplacer par char[i] == char[j] ?

Le précédent texte n'est pas très formel mais j'espère que vous aurez compris mon soucis.


Pierre

C'est pour déterminer une égalité où une précédence? Les chaînes sont elles le plus souvent différentes?

Citation:

---

Envoyé par _skip

C'est pour déterminer une égalité où une précédence? Les chaînes sont elles le plus souvent différentes?

---

Je reformule ma phrase ci-dessus.
Je ne fais que des comparaison de caractères à caractères, que ce soit des caractères appartenant aux chaines ou des caractères définis à l'avance.

Pour donner une idée de la fonction, voilà un exemple de ce qu'elle pourrait être :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

boolean compare(String str1, String str2) { char c = str1.charAt(0); if (c == '[') { char c2 = str1.charAt(str1.length()-1); if (c2 == ']') { ... } } else if (c == '"') { for (i=1;i<str1.length-2;i++) { if (str1.charAt(i) == str2.charAt(i)) { ... } } } else if (c == str2.charAt(0)) { ... } }

---

je serais toi, je vérifierais plutot l'algorithme qui fait appel à compare. C'est probablement là que tu peux gagner énormément de temps. Tu va "peut-être" pouvoir augmenter de 1 ou 2% la vitesse ton compare en travaillant avec des char[], mais tu ne résoudra pas ton problème de base, ton compar est saturé d'appel et il faut voir à limiter les appels.

PS: avoir le code complet de la méthode aiderait peut être aussi, on a qu'un vague code là. Quel est le temps de calcul de ta méthode en fonction de la taille des strings? o(1), o(n)?, o(n²) ? .....

Personnellement, question de rapidité je ferais un

int result = string1.indexof(string2);

tu peux aussi faire :

int result = string1.indexof(string2,2);

Ici, tu fais une comparaison à partir du deuxieme caractere de string1.

Citation:

---

Envoyé par tchize_

je serais toi, je vérifierais plutot l'algorithme qui fait appel à compare.

---

+1

Citation:

---

Envoyé par tchize_

PS: avoir le code complet de la méthode aiderait peut être aussi, on a qu'un vague code là. Quel est le temps de calcul de ta méthode en fonction de la taille des strings? o(1), o(n)?, o(n²) ? .....

---

Et plus que tout il faudrait savoir ce que doit faire précisément ta méthode compare()...

a++

La création d'un char[] à partir d'un String est couteux aussi.
Si t'a un char[] en entrée fait la comparaison directement sinon le gain de temps sera vraiment minime si ce n'est moins performant à cause du cout de la méthode String.toCharArray() donc à part améliorer ton algorithme, je ne vois ce que tu peux faire d'autre.

cdlt

Citation:

---

Envoyé par tchize_

je serais toi, je vérifierais plutot l'algorithme qui fait appel à compare. C'est probablement là que tu peux gagner énormément de temps.

---

Après m'avoir convaincu que la différence entre char[] et String n'était pas flagrante, j'ai essayé ta méthode.
Pour ça, je me suis basé sur la propriété de compare qui est -si je ne me trompe pas de mot- transitive. (compare(x,y) et compare(y,z) => compare(x,z)).

J'ai donc gardé en mémoire tous les appels à compare et créé un ordre partiel sur les String. Avant chaque appel à compare, je regarde si les 2 formules à comparer sont dans l'ordre partiel, si non, je les insère. Ensuite, pour savoir si compare(x,y), il suffit de regarder dans cet ordre si x est inférieur à y.

Le code est ainsi plus long à l'initialisation (4 min à la place de 30 sec), mais les appels à compare passent de 120 ms en moyenne à 20, avec un test comprenant 1000000 chaines aléatoires.

Merci pour vos explications techniques.

une autre possibilité, si c'est un algo de tri qui fait appel à compare, c'est de regarder dans les algorithmes optimisés existant (quicksort, heapsort) si tu trouve pas ton bonheur. La différence de vitesse relative entre un heapsort et un bubblesort, sur un million d'entrée est de l'ordre de 160.000 fois plus rapide dans les cas extrèmes.

Citation:

---

Envoyé par tchize_

une autre possibilité, si c'est un algo de tri qui fait appel à compare, c'est de regarder dans les algorithmes optimisés existant (quicksort, heapsort) si tu trouve pas ton bonheur. La différence de vitesse relative entre un heapsort et un bubblesort, sur un million d'entrée est de l'ordre de 160.000 fois plus rapide dans les cas extrèmes.

---

Je me souviens avoir réalisé une étude il y a quelques années pour prouver les différences entre les différents algos de tri, et je te soutiens dans tes propos, les résultats donnent effectivement des chiffres de la sorte.

Cependant, je ne cherche pas à trier une liste grâce à compare, mais bien de réaliser un ordre partiel. Pour les moins matheux d'entre nous, wikipedia en donne une bonne définition.


Pierre