hackerrank challenges question

Version imprimable

Bonjour, j'aimerais un peu d'aide sur un exercice en java que j'ai trouvé sur hackerank à cette adresse:
https://www.hackerrank.com/challenge...d-maps/problem

Je me suis débrouillé pour faire l'exercice mais mon code est mal optimisé et dès que l'on me donne 10000 possibilité (ou plus ou moins, je ne sais pas), j'ai un time out sur le site.
Si je pouvais avoir des conseils claires et pas trop compliqués pour améliorer mon code actuel tout en gardant le même cheminement logique.

A mon avis, le problème vient de la dernière partie, lors de l'analyse. Devoir vérifier 10000 entrées pour dire not found à la fin.
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 package hackerRank; import java.util.HashMap; import java.util.Scanner; public class day8 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); HashMap<String, Integer> myMap = new HashMap<String, Integer>(); int nb = sc.nextInt(); String [] tab1 = new String[nb]; sc.nextLine(); for(int k = 0; k < nb; k++) { String str = sc.nextLine(); tab1 = str.split(" "); myMap.put(tab1[0], Integer.parseInt(tab1[1])); } while(sc.hasNext()){ String s = sc.nextLine(); boolean bool = false; for (String item : myMap.keySet()) { if(item.equals(s)) { System.out.println(item+"="+myMap.get(item)); bool = true; } } if(bool == false) { System.out.println("Not found"); } } sc.close(); } }
Merci beaucoup et bon fin de 1er mai.

Bon, une bonne âme qui se nomme Winjerome m'a parlé de containsKey:

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
 
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		HashMap<String, Integer> myMap = new HashMap<String, Integer>();
 
		int nb = sc.nextInt();
		String [] tab1 = new String[nb];
 
		sc.nextLine();
		for(int k = 0; k < nb; k++) {
			String str = sc.nextLine();	
			tab1 = str.split(" ");	
			myMap.put(tab1[0], Integer.parseInt(tab1[1]));
		}
 
		while(sc.hasNext()){
			String s = sc.nextLine();
 
			if(myMap.containsKey(s)) {
				System.out.println(s+"="+myMap.get(s));
 
			}else {
				System.out.println("Not found");
			}
		}
 
		sc.close();
	}

Le test marche :) Bonne soirée

Salut,
au sujet de containsKey : le but d'une map est d'associer des clefs avec des valeurs afin de retrouver rapidement la valeur associée lorsqu'on a la clef. Il est donc effectivement contre productif de parcourir le keyset pour retrouver la clef ou l'entryset pour retrouver un mapping dans ce cas. Et, en tout cas, c'est justement le but de l'exercice que d'utiliser les méthodes de mapping et non de parcours.
Tu peux optimiser lorsque tu as besoin de la valeur associée à la clef. Au lieu d'un
Code:

1 2 3 4 5 6 7 if ( map.containsKey(key) ) { value = map.get(key); System.out.println("clef=" + key + " valeur="+value); } else { System.out.println("clef=" + key + " valeur=pas trouvée"); }
Tu peux faire :
Code:

1 2 3 4 5 6 7 value = map.get(key); if ( value!=null ) { System.out.println("clef=" + key + " valeur="+value); } else { System.out.println("clef=" + key + " valeur=pas trouvée"); }
Si la map ne peut contenir de valeur null associée à une clef, ce sera un peu plus rapide. Négligeable probablement sur quelques accès, mais sur 10000 ça peut commencer à se sentir.
Rien ne nécessite la conversion des numéros téléphoniques en int (d'ailleurs ça n'a pas de sens logique : un numéro de téléphone est un code, pas un nombre, même s'il n'est constitué que de chiffres). Tu économiseras des conversions inutiles en traitant tout en String (donc Map<String,String>) et le programme n'en sera que plus simple.
Cette ligne est non seulement inutile mais illogique :

Code:

String [] tab1 = new String[nb];

Le tableau tab1 est le résultat du split de chaque ligne du type "<nom> <numéro de téléphone>" soit 2 valeurs maximum. Il n'y a aucune raison de réserver un tableau de nb String, nb étant le nombre de lignes d'association nom/numéro de téléphone, rien à voir avec le nombre d'informations dans une ligne (2). En plus, tu réserves un tableau qui ne sera jamais utilisé : consommation inutile de mémoire et de temps.
Il est d'ailleurs inutile de déclarer ce tableau à cet endroit d'ailleurs. Tu peux écrire :

Code:

Sting[] tab1 = str.split(" ");

En revanche, pour optimiser, tu pourrais prédimensionner la table de la map avec nb :
Code:

1 2 3 int nb = sc.nextInt(); Map<String, String> myMap = new HashMap<>(nb);
On pourrait toujours tester si le split pourrait être remplacé par une utilisation de indexOf et substring (l'impact est peut-être négligeable dans les conditions d'exécution). Ce n'est pas tant sur le split, mais sur la déclaration de milliers de tableaux. Cette création n'aura pas d'impact sur la boucle de lecture elle-même mais sur le processus de garbage recollection en cas de besoin de mémoire.
Tu peux omettre sc.close();. Tu n'a pas ouvert System.in, tu n'as pas à le fermer.

Bonsoir ! Merci beaucoup, réponse très pertinente. Au final, j'avais gardé le 'Integer' dans le Map parce que j'avais cru bêtement que c'était ce qui était demandé, histoire de m'embêter :)
Mise à part le sc.close() que je croyais devoir toujours faire dès que j'utilisais un Objet scanner, j'ai compris tes remarques !

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
 
package hackerRank;
 
import java.util.HashMap;
import java.util.Scanner;
 
public class day8 {
 
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
		int nb = sc.nextInt();
		HashMap<String, String> myMap = new HashMap<String, String>(nb);
 
		sc.nextLine();
		for(int k = 0; k < nb; k++) {
			String str = sc.nextLine();	
			String[] tab1 = str.split(" ");	
			myMap.put(tab1[0], tab1[1]);
		}
 
		while(sc.hasNext()){
			String key = sc.nextLine();
			String value = myMap.get(key);
 
			if(value != null) {
				System.out.println(key+"="+value);
 
			}else {
				System.out.println("Not found");
			}
		}
 
//		sc.close();
	}
 
}