Discussion :

[ForgetTheNorm]

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

[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.

[erictoguem]

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

[ForgetTheNorm]

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

[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.

[ForgetTheNorm]

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

[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.

[le y@m's]

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.

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.

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 .

[tchize_]

exact, merci de m'avoir corrigé

[adiGuba]

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++

[_skip]

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.

[tchize_]

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

[ForgetTheNorm]

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

[_skip]

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

[ForgetTheNorm]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)) {
    ...
  }
}

[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. 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²) ? .....

[X-plode]

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.

[adiGuba]

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

+1

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++

[hibour]

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

[ForgetTheNorm]

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.