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

**Terminator** · 10/05/2007, 15h51

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 :

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

1
2
String monString = "tu";
String tab = {"vous","je","tu"};

Je voudrais un truc simple du genre

Code :

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

1
2
3
4
if (monString.isContenuDans(tab))
{
...
}

Je recherche donc le nom anglais de "isContenuDans"

D'avance merci

**chtig** · 10/05/2007, 15h55

Il n'y a pas ça avec les tableaux, mais avec les collections oui.
Regarde ArrayList ....

**adiGuba** · 10/05/2007, 16h00

Salut,

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

a++

**®om** · 10/05/2007, 16h10

Code :

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

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

**guis14** · 10/05/2007, 16h11

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");

++

**leyee** · 10/05/2007, 16h14

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

**guis14** · 10/05/2007, 16h48

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.

**CyberChouan** · 10/05/2007, 17h13

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

**guis14** · 10/05/2007, 17h23

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

++

**®om** · 10/05/2007, 19h41

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

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 :

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

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

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

**Terminator** · 10/05/2007, 20h17

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

**Terminator** · 10/05/2007, 20h18

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

**®om** · 10/05/2007, 20h40

Envoyé par Terminator

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

Oui

Le contains est bien plus rapide...

**adiGuba** · 10/05/2007, 22h42

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 :

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

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 :

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

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

**®om** · 10/05/2007, 22h56

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é

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)?

**nicØB** · 11/05/2007, 08h36

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 :

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

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

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

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

@+

**adiGuba** · 11/05/2007, 08h50

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

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

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

)

a++

**Terminator** · 11/05/2007, 11h06

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

**leyee** · 11/05/2007, 11h12

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

**nicØB** · 11/05/2007, 11h42

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 ?

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

Langage Java

Discussions similaires

Partager

Partager