Comparer un String et un String[] sans "for"

Version imprimable

10/05/2007, 15h51
Terminator

Comparer un String et un String[] sans "for"
Bonjour,

J'aimerais savoir si il existe une méthode permettant de comparer un string avec un tableau de string[] sans pour autant faire une boucle for.
Exemple
Code:

1 2 String monString = "tu"; String tab = {"vous","je","tu"};
Je voudrais un truc simple du genre
Code:

1 2 3 4 if (monString.isContenuDans(tab)) { ... }
Je recherche donc le nom anglais de "isContenuDans"

D'avance merci
10/05/2007, 15h55
chtig

Il n'y a pas ça avec les tableaux, mais avec les collections oui.
Regarde ArrayList ....
10/05/2007, 16h00
adiGuba

Salut,

:arrow: http://javasearch.developpez.com/j2s...va.lang.Object[],%20java.lang.Object)

a++

Code:

1
2
3
if(Arrays.asList(tab).contains(monString) {
    ...
}

10/05/2007, 16h11
guis14

Salut,

alors grosso modo tu transforme ton tableau de string en liste grace a Arrays.asList(String []); et puis tu fait un contains sur ta liste
Liste.contains("ta string");

++
10/05/2007, 16h14
leyee

Je ne vois pas trop l'interet en gain de performance d'une telle chose : pour faire le test contains, la collection sera bien au (partiellement) parcourue tot ou tard...
10/05/2007, 16h48
guis14

oui sauf que le code est plus simple a ecrire et que l'optimisation de contains est sans mesure par rapport a celle de ton for iteratif.
10/05/2007, 17h13
CyberChouan

Citation:

Envoyé par guis14

l'optimisation de contains est sans mesure par rapport a celle de ton for iteratif.

Bof... Si jamais tu installes un JDK, tu pourras t'amuser à aller voir les sources des classes java fournies par Sun. Tu t'apercevras que la méthode "contains" effectue une simple boucle itérative de recherche (du moins, c'est le cas dans java 1.4) ;)
C'est juste plus clair à écrire mais pas plus efficace que de réécrire la méthode de recherche à la main.

On ne peut vraiment optimiser la recherche que dans le cas de listes triées (dichotomie...)
10/05/2007, 17h23
guis14

Salut,

j'ai regarder les source en effet l'appel a contains fait appel a indoexOf qui fait une boucle for. Histoire d'etre vraiment sur je ferait un petit coup de profiling quand j'aurais deux minute pour voir le resultat....

++

Citation:

Envoyé par leyee

Je ne vois pas trop l'interet en gain de performance d'une telle chose : pour faire le test contains, la collection sera bien au (partiellement) parcourue tot ou tard...

Citation:

Envoyé par guis14

oui sauf que le code est plus simple a ecrire et que l'optimisation de contains est sans mesure par rapport a celle de ton for iteratif.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public class TestBoucle { public static void main(String... args) { final Random RANDOM = new Random(); final int TAB_SIZE = 100; final int NB_ITER = 10000; boolean contains; Integer[] tab = new Integer[TAB_SIZE]; for (int i = 0; i < TAB_SIZE; i++) { tab[i] = RANDOM.nextInt(TAB_SIZE); } long t = System.nanoTime(); for (int i = 0; i < NB_ITER; i++) { int j = 0; int r = RANDOM.nextInt(TAB_SIZE); while (j < TAB_SIZE && !tab[j].equals(r)) { j++; } contains = j <= TAB_SIZE; } System.out.println(System.nanoTime() - t); List<Integer> list = Arrays.asList(tab); t = System.nanoTime(); for (int i = 0; i < NB_ITER; i++) { contains = list.contains(RANDOM.nextInt(TAB_SIZE)); } System.out.println(System.nanoTime() - t); } }
Code:

1 2 137111504 131072190
En fait je voulais montrer que la différence était négligeable, mais le contains a l'avantage :)
Je ne comprends pas pourquoi (j'imagine que le JIT y est pour quelque chose), vive l'optimisation :)

EDIT: maintenant ça se tient :)

10/05/2007, 20h17
Terminator

Bonsoir,

je vois que ma question a soulevée ne polémique :)

Alors bien entendu, ce n'est pas pour un gain de performance que j'ai demandé ceci (je pensais même que j'allais y perdre car faire appel à une classe qui fait également une boucle alors qu'on faisant directement la boucle on économise l'appel).

Bref, je voulais juste un truc qui tienne sur une ligne au lieu de faire moi-même la boucle.

MERCI ENCORE A VOUS TOUS
10/05/2007, 20h18
Terminator

D'apres ton test, la différence est enorme, non?
10/05/2007, 20h40
®om

Citation:

Envoyé par Terminator

D'apres ton test, la différence est enorme, non?

Oui :)
Le contains est bien plus rapide...

Citation:

Envoyé par ®om

Le contains est bien plus rapide...

Attention aux tests qui peuvent être menteur ;)

Déjà tu devrais éviter d'utiliser des nombres aléatoires, ou plus précisément utiliser les mêmes nombres dans les deux cas pour éviter de petit effets de bord...

Ensuite ta boucle est largement défavorisé à cause du nextInt() de la seconde boucle qui régénère un nombre aléatoire à chaque indice... sans oublier qu'il y a un auto-unboxing à chaque fois qui peut fausser les choses...

Enfin il faut se méfier du GarbageCollector et du compilateur JIT. Le premier peut fausser les résultats lorsqu'il s'exécute (il faut donc essayer d'utiliser le minimum d'objet temporaire pendant le test, voir même de forcer le GC entre deux tests), et le second optimise le code en court de route, et qui fausse généralement les premiers résultats (dans ton exemple en inversant les deux tests j'obtiens un résultat inverse).

Tu peux vérifier cela en utilisant les options -verbose:gc (pour surveiller le travail du GC) et -XX:+PrintCompilation pour la compilation JIT.

J'ai exécuté ton code avec ces options et j'obtiens ceci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  1       java.lang.String::hashCode (60 bytes)
---   n   sun.misc.Unsafe::compareAndSwapLong
  2       java.lang.String::charAt (33 bytes)
  3  !    sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (698 bytes)
  4       java.util.Random::nextInt (60 bytes)
  5       java.util.Random::next (47 bytes)
  6       java.util.concurrent.atomic.AtomicLong::get (5 bytes)
  7       java.util.concurrent.atomic.AtomicLong::compareAndSet (13 bytes)
  8       java.lang.Integer::valueOf (31 bytes)
  9       java.lang.Integer::equals (29 bytes)
  1%      com.developpez.adiguba.Main::main @ 69 (196 bytes)
520559923
 10       java.util.Arrays$ArrayList::indexOf (69 bytes)
 11       java.util.Arrays$ArrayList::contains (15 bytes)
51712448

Le GC ne s'exécute pas mais le JIT met à mal ta première boucle...

Pour cela il est également préférable d'exécuter plusieurs fois le même test, et éviter de prendre en compte les résultats qui sorte un peu trop de la moyenne...

Exemple avec ce code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
	public static void main(String... args) {
		final Random RANDOM = new Random();
		final int TAB_SIZE = 100;
		final int NB_ITER = 10000;
 
		Integer[] tab = new Integer[TAB_SIZE];
		for (int i = 0; i < TAB_SIZE; i++) {
			tab[i] = RANDOM.nextInt(TAB_SIZE);
		}
 
		List<Integer> list = Arrays.asList(tab);
 
		boolean bContains;
		long t;
 
		// On recherche toujours la dernière valeur
		// (afin de tester tout l'algorythme) 
		Integer toSearch = tab[tab.length-1];
 
		// On exécute chaque test 8 fois
		for (int x=0; x<8; x++) {
 
			// On "force" la libération de la mémoire
			// --> A ne pas faire dans une vrai application !!!!
			System.gc(); Thread.yield();
 
 
			// Cas 1 : la boucle
			bContains = false;
			t = System.nanoTime();
			for (int i = 0; i < NB_ITER; i++) {
				for (int j=0; j<tab.length; j++) {
					if (tab[j].equals(toSearch)) {
						bContains = true;
						break;
					}
				}
			}
			t = System.nanoTime()-t;
			System.out.printf("Boucle     : %s : %15d / %4d ms%n", bContains, t, t/1000000L);
 
			// Cas 2 : contains()
			bContains = false;
			t = System.nanoTime();
			for (int i = 0; i < NB_ITER; i++) {
				bContains = list.contains(toSearch);
			}
			t = System.nanoTime()-t;
			System.out.printf("Contains   : %s : %15d / %4d ms%n", bContains, t, t/1000000L);
 
		}
 
	}

J'obtiens ceci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
  1       java.lang.String::hashCode (60 bytes)
[Full GC 200K->111K(5056K), 0.0544580 secs]
  2       java.lang.String::charAt (33 bytes)
  3  !    sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (698 bytes)
  4       java.lang.Integer::equals (29 bytes)
  1%      com.developpez.adiguba.Main::main @ 101 (287 bytes)
  5  !    sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (1814 bytes)
Boucle     : true :       161299996 /  161 ms
  6       java.lang.Object::<init> (1 bytes)
  7  !    java.io.BufferedReader::readLine (304 bytes)
  8       java.lang.String::indexOf (151 bytes)
  9       java.lang.String::equals (88 bytes)
 10       java.lang.String::lastIndexOf (156 bytes)
 11       java.io.UnixFileSystem::normalize (75 bytes)
 12       java.lang.String::indexOf (166 bytes)
 13       java.util.Arrays$ArrayList::indexOf (69 bytes)
 14       java.util.Arrays$ArrayList::contains (15 bytes)
Contains   : true :        97917810 /   97 ms
[Full GC 235K->145K(5056K), 0.0329490 secs]
Boucle     : true :        41646670 /   41 ms
Contains   : true :        51397048 /   51 ms
[Full GC 163K->145K(5056K), 0.0448590 secs]
Boucle     : true :        42671074 /   42 ms
Contains   : true :        41351714 /   41 ms
[Full GC 163K->144K(5056K), 0.0408030 secs]
Boucle     : true :        32151931 /   32 ms
Contains   : true :        54798419 /   54 ms
[Full GC 162K->144K(5056K), 0.0340710 secs]
Boucle     : true :        42507343 /   42 ms
Contains   : true :        31152476 /   31 ms
[Full GC 162K->144K(5056K), 0.0454590 secs]
Boucle     : true :        29045594 /   29 ms
 15       java.util.regex.Matcher::reset (83 bytes)
Contains   : true :        55578366 /   55 ms
[Full GC 162K->144K(5056K), 0.0385500 secs]
Boucle     : true :        41149785 /   41 ms
Contains   : true :        38473475 /   38 ms
[Full GC 162K->144K(5056K), 0.0412500 secs]
Boucle     : true :        38743137 /   38 ms
Contains   : true :        45195390 /   45 ms

La différences est déjà moins grande et varie surement à cause de la charge du système et peut être considéré comme insignifiante à mon avis...

a++

10/05/2007, 22h56
®om

Oui, bien sûr si les différences sont petites, le test n'est pas valable, mais si le test est correct (il ne l'était pas) et qu'il y a un rapport de 10 à chaque fois... on peut quand même avoir un avis tranché :)

Citation:

Envoyé par adiGuba

-XX:+PrintCompilation

Ça fait quoi exactement?

Y'a-t-il un moyen de récupérer le code assembleur à partir du binaire engendré par le JIT (donc récupérer le binaire)?

Salut,

Sinon, ici, au lieu d'une List il vaudrait mieux utiliser un Set.
Enfin ca dépend de la taille de son tableau aussi.

Résultats (avec le code de adiGuba et 1000 éléments) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Boucle           : true :       123750644 /  123 ms
Contains (list)  : true :       109326744 /  109 ms
Contains (set)   : true :         1436774 /    1 ms
Boucle           : true :       107048242 /  107 ms
Contains (list)  : true :        96554730 /   96 ms
Contains (set)   : true :          401728 /    0 ms
Boucle           : true :       104875340 /  104 ms
Contains (list)  : true :        98991911 /   98 ms
Contains (set)   : true :          403683 /    0 ms
Boucle           : true :       103315924 /  103 ms
Contains (list)  : true :        95155948 /   95 ms
Contains (set)   : true :          397816 /    0 ms
Boucle           : true :       101289689 /  101 ms
Contains (list)  : true :        95680876 /   95 ms
Contains (set)   : true :          397816 /    0 ms
Boucle           : true :       105086540 /  105 ms
Contains (list)  : true :        95099796 /   95 ms
Contains (set)   : true :          397816 /    0 ms
Boucle           : true :       102878997 /  102 ms
Contains (list)  : true :        96182057 /   96 ms
Contains (set)   : true :          393626 /    0 ms
Boucle           : true :       101515137 /  101 ms
Contains (list)  : true :        94746399 /   94 ms
Contains (set)   : true :          396978 /    0 ms

Bon par contre il n'y a pas de Arrays.asSet ...
Donc ça ferait quelque chose comme ça :

Code:

Set<Integer> set = new HashSet<Integer>(Arrays.asList(tab));

La création du Set est plus lente du coup si on fait comme cela.

@+

11/05/2007, 08h50
adiGuba

Citation:

Envoyé par ®om

Ça fait quoi exactement?

-XX:+PrintCompilation permet de voir ce que fait le compilateur JIT, et en particulier les méthodes qu'il compile à la volée.

On peut ainsi voir que le premier passage est fortement pénalisé par la compilation de la plupart des méthodes, alors que lors de la seconde boucle il n'y a que très peu de méthode qui sont compilé (les autres l'ont déjà été auparavant...

Citation:

Envoyé par ®om

Y'a-t-il un moyen de récupérer le code assembleur à partir du binaire engendré par le JIT (donc récupérer le binaire)?

Aucune idée...

Citation:

Envoyé par nicØB

La création du Set est plus lente du coup si on fait comme cela.

Et aussi plus consommateur en mémoire (pour ce qui concerne le HashSet en tout cas).

Mais bon dans tous les cas la différence n'est pas vraiment intéressante dans une application "normale" (qui a déjà vérifié plus de 10000 fois qu'un élément appartient à un tableau :aie:)

a++
11/05/2007, 11h06
Terminator

Bonjour et merci à tous,
Pour tout vous dire, la performance est importante!!
En effet, je compare pas moins de 35.000 chaines de caracteres avec un tableau qui ne comporte que 20 chaines.

Donc j'ai une sorte de boucle de 1 à 35.000 vérifiant la presence ou pas de la chaine dans mon string[20];

Merci à tous d'avoir pris le temps de lancer la discution (la polémique?).
11/05/2007, 11h12
leyee

Tu es sur que ton application necessite tant de verification (tu n'as pas de moyen de trouver un algo moins violent ?). Sinon, il ne s'agit pas de polémique, la performance du code est un sujet qui me tiens à coeur personnellement
11/05/2007, 11h42
nicØB

Citation:

Envoyé par Terminator

En effet, je compare pas moins de 35.000 chaines de caracteres avec un tableau qui ne comporte que 20 chaines.

Dans ce cas là, je dirais qu'il vaut mieux utiliser un Set pour stocker tes 20 chaînes.
Je suppose que la comparaison sera plus rapide vu qu'il faut d'abord comparerr les hash, et le equals est effectué si les 2 hash en question sont égaux.
Je me trompe ?