[trie value de HashMap] Soucis de performances

**ChipsterJulien** · 31/12/2009, 19h13

Bonsoir d'un débutant

Après pas mal de recherche sur le forum, j'ai bien trouvé des exemples avec compareTo mais je ne suis jamais arrivé à mettre ça en oeuvre. Du cou j'ai fait ma propre méthode mais niveau performance c'est une catastrophe. 400 000 IP en 8 min sachant que la conso se fait à 99,99% dans mon algo de trie pourri

Si quelqu'un pouvait m'indiquer la ou les démarche(s) à suivre pour améliorer les codes suivant :

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
import java.util.regex.*;
 
public class Main {
	public static void main(String[] args) {
		LireFichier fichier = null;
		EcrireFichier cible = null;
		Pattern p = Pattern.compile("SRC=(\\S+)");
 
		try {
			fichier = new LireFichier(args[0]);
		}
		catch(ArrayIndexOutOfBoundsException e) {
			System.out.println("Nombre d'arguments incorrect");
			System.exit(1);
		}
 
		Ip adresse = new Ip();
		String lecture = "";
 
		while((lecture = fichier.getLigne()) != null) {
			Matcher m = p.matcher(lecture);
			while(m.find())
				adresse.addIp(m.group(1));
		}
		fichier.closeFichier();
		System.out.println("lecture terminée");
		adresse.trie();
		System.out.println("Triage terminé");
		try {
			cible = new EcrireFichier(args[1]);
		}
		catch(ArrayIndexOutOfBoundsException e) {
			System.out.println("Nombre d'arguments incorrect");
			System.exit(1);
		}
		for(int i = 0; i < adresse.getSize(); ++i) {
			cible.write(adresse.getIp(i) + " => " + adresse.getNb(i));
		}
		cible.close();
		System.out.println("écriture terminée");
	}
}

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
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.FileNotFoundException;
 
public class EcrireFichier {
	private String nomFichier = "";
	private BufferedWriter bw = null;
 
	public EcrireFichier(String arg) {
		this.setNomFichier(arg);
 
		try {
			bw = new BufferedWriter(new FileWriter(nomFichier));
		}
		catch(FileNotFoundException e) {
			System.out.println("Fichier introuvable");
			System.exit(1);
		}
		catch(IOException e) {
			System.out.println("Erreur d'E/S");
			System.exit(1);
		}
	}
 
	public void write(String ligne) {
		try {
			bw.write(ligne + "\n");
		}
		catch(IOException e) {
			System.out.println("Erreur d'E/S");
			System.exit(1);
		}
	}
 
	public void setNomFichier(String nomFichier) {
		this.nomFichier = nomFichier;
	}
 
	public void close() {
		if(bw != null) {
			try {
				bw.flush();
				bw.close();
			}
			catch(IOException e) {
				System.out.println("Erreur d'E/S");
				System.exit(1);
			}
		}
	}
}

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
54
55
56
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.FileNotFoundException;
 
public class LireFichier {
	private String nomFichier = "";
	private BufferedReader rd = null;
 
	// Constructeur
	public LireFichier(String arg) {
		this.setNomFichier(arg);
		try {
			rd = new BufferedReader(new FileReader(nomFichier));
		}
		catch(FileNotFoundException e) {
			System.out.println("Fichier introuvable");
			System.exit(1);
		}
		catch(IOException e) {
			System.out.println("Erreur d'E/S");
			System.exit(1);
		}
	}
 
	// Fermeture du fichier
	public void closeFichier() {
		try {
			rd.close();
		}
		catch(IOException e) {
			System.out.println("Erreur d'E/S");
			System.exit(1);
		}
	}
 
	// Accesseurs et mutateurs
	public String getNomFichier() {
		return this.nomFichier;
	}
	public void setNomFichier(String nomFichier) {
		this.nomFichier = nomFichier;
	}
 
	public String getLigne() {
		String str = "";
		try {
			str = rd.readLine();
		}
		catch(IOException e) {
			System.out.println("Erreur d'E/S");
			System.exit(1);
		}
		return str;
	}
}

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
54
55
56
57
58
59
60
61
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Collection;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;
import java.util.Iterator;
 
public class Ip {
	private HashMap<String, Integer> hm = new HashMap<String, Integer>();
	private String[] tableauIp;
	private int[] tableauNombre;
 
	public void addIp(String ip) {
		if(hm.containsKey(ip)) {
			hm.put(ip, (hm.get(ip) + 1));
		}
		else {
			hm.put(ip, 1);
		}
	}
	public void trie() {
		tableauIp      = new String[hm.size()];
		tableauNombre  = new int[hm.size()];
		int emplacementTab = 0;
 
		Collection<Integer> valeur = hm.values();
		List<Integer> liste = new ArrayList<Integer>(valeur);
		Collections.sort(liste);
		for(int i = (liste.size() - 1), j = 0; i >= 0; --i, ++j) {
			Set e = hm.keySet();
			Iterator clef = e.iterator();
			Boolean trouve = false;
 
			while(clef.hasNext() && !trouve) {
				String key = (String)clef.next();
 
				if(hm.get(key) == liste.get(i)) {
					trouve           = true;
					tableauIp[j]     = key;
					tableauNombre[j] = hm.get(key);
 
					++emplacementTab;
					hm.remove(key);
				}
			}
		}
		hm.clear();
	}
 
	public String getIp(int i) {
		return tableauIp[i];
	}
	public int getNb(int i) {
		return tableauNombre[i];
	}
	public int getSize() {
		return tableauIp.length;
	}
}

Meilleur voeux pour cette nouvelle année

**Uther** · 01/01/2010, 09h28

Une HashMap ne peut tout simplement pas être trié car elle n'a pas d'ordre garanti. Si tu veux avoir une notion d'ordre, il te faut une LinkedHashMap.

Je ne suis pas sur d'avoir compris si tu souhaites trier en fonction de la clé ou de la valeur. Si tu veux trier en fonction de la clé, la TreeMap est ce qu'il te faut. Son contenu est automatiquement trié.

**ChipsterJulien** · 01/01/2010, 10h23

J'avais utilisé une treemap au début mais ... ce n'est pas ce qu'il me fallait car justement je souhaitais trier en fonction des valeurs et non des clefs. Je vais regarder du coté des linkedHashMap et je vous tiens au courant sur les performances et surtout si j'arrive à l'implémenter

[edit] j'avais zappé ceci : http://java.developpez.com/faq/java/...IONS_trier_map
donc je vais essayer de mettre ça en oeuvre.

Si vous avez d'autres idées ainsi que des remarques à apporter sur ce que j'ai fait, ..., n'hésitez pas

**ChipsterJulien** · 01/01/2010, 18h44

Malgré toute ma bonne volonté je n'arrive pas à faire quelque chose de fonctionnel. Soit ça ne compile pas soit ça me fait absolument n'importe quoi

**Uther** · 02/01/2010, 09h32

Voici un code qui devrait fonctionner:

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
    public static <K, V extends Comparable> void sortByValue(LinkedHashMap<K, V> map) {
        // Crée une liste contenant toutes les entrées de la map
        List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
 
        // Trie la liste en fonction de la valeur des entrées de la map
        Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
            public int compare(Entry<K, V> o1, Entry<K, V> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
 
        // Vide la Map et la remplit avec les entrées dans le bon ordre
        map.clear();
        for (Map.Entry<K, V> entry : list) {
            map.put(entry.getKey(), entry.getValue());
        }
 
    }

**ChipsterJulien** · 06/01/2010, 20h44

Je regarde ça. Merci pour la réponse

**ChipsterJulien** · 07/01/2010, 11h12

J'ai modifié le code comme 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
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.LinkedHashMap;
import java.util.TreeMap;
import java.util.Collection;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Set;
import java.util.Iterator;
import java.lang.Comparable;
import java.util.*;
 
public class Ip {
	private LinkedHashMap<String, Integer> hm = new LinkedHashMap<String, Integer>();
	private String[] tableauIp;
	private int[] tableauNombre;
 
	public void addIp(String ip) {
		if(hm.containsKey(ip)) {
			hm.put(ip, (hm.get(ip) + 1));
		}
		else {
			hm.put(ip, 1);
		}
	}
 
	public String getIp(int i) {
		return tableauIp[i];
	}
	public int getNb(int i) {
		return tableauNombre[i];
	}
	public int getSize() {
		return tableauIp.length;
	}
 
	public static <K, V extends Comparable> void sortByValue(LinkedHashMap<K, V> map) {
		// Crée une liste contenant toutes les entrées de la map
		List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
 
		// Trie la liste en fonction de la valeur des entrées de la map
		Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
			public int compare(Entry<K, V> o1, Entry<K, V> o2) {
				return o1.getValue().compareTo(o2.getValue());
			}
		});
 
		// Vide la Map et la remplit avec les entrées dans le bon ordre
		map.clear();
		for (Map.Entry<K, V> entry : list) {
			map.put(entry.getKey(), entry.getValue());
		}
	}
}

mais à la compilation il me donne ceci

Code :

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

1
2
3
4
5
6
7
8
9
./Ip.java:43: cannot find symbol
symbol: class Entry
			public int compare(Entry<K, V> o1, Entry<K, V> o2) {
			                   ^
./Ip.java:43: cannot find symbol
symbol: class Entry
			public int compare(Entry<K, V> o1, Entry<K, V> o2) {
			                                   ^
2 errors

**Uther** · 07/01/2010, 11h45

Importes java.util.Map.Entry ou utilises Map.Entry<K, V> a la place de Entry<K, V>

**ChipsterJulien** · 07/01/2010, 13h19

Je l'avais déjà fait et j'obtenais ceci :

Code :

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

1
2
Note: ./Ip.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details

une fois rajouté

Code :

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

javac Main.java -Xlint:unchecked

Aucune erreur donc j'ai trouvé ça louche

**ChipsterJulien** · 07/01/2010, 13h31

Dans le précédent message, j'ai oublié de spécifier que je n'arrivais pas à utiliser la fonction que tu m'avais donné

Bon, je ne peux pas supprimer ce message.

Pouce donc, je pense avoir trouver donc j'essaie de trouver par moi même c'est plus instructif et c'est plus marrant aussi

**ChipsterJulien** · 07/01/2010, 14h46

J'ai rajouté :

Code :

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

Collection.reverse(list)

pour l'avoir dans l'ordre décroissant. J'arrive à faire l'affichage avec un iterator dans le classe Ip.java

Il me reste à trouver comme faire une vrai fonction pour renvoyer entrée par entrée sur Main.java

**ChipsterJulien** · 07/01/2010, 15h56

J'ai rajouté une fonction :

Code :

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

1
2
3
public void trie() {
    sortByValue(affiche);
}

car je n'arrive pas à l'utiliser directement dans le fichier Main.java

Ensuite j'essaie d'écrire une fonction pour avoir une fonction qui me revoit une clef à chaque fois que je l'appelle mais je bloque là aussi

**Rei Ichido** · 07/01/2010, 16h41

Pourquoi ne pas faire simple ?

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
54
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class IP {
 
	public class SingleIP implements Comparable<SingleIP> {
 
		private String ip;
 
		private Integer nb;
 
		public SingleIP(String ip) {
			this.ip = ip;
			this.nb = 1;
		}
 
		public int compareTo(SingleIP p_o) {
			return this.nb.compareTo(p_o.nb);
		}
	}
 
	private Map<String, SingleIP> hm = new HashMap<String, SingleIP>();
	private ArrayList<SingleIP> list;
 
	public void addIp(String ip) {
		if(hm.containsKey(ip)) {
			SingleIP s_ip = hm.get(ip);
			s_ip.nb = s_ip.nb + 1;
		}
		else {
			hm.put(ip, new SingleIP(ip));
		}
	}
	public void trie() {
		List<SingleIP> liste = new ArrayList<SingleIP>(hm.values());
		Collections.sort(liste);
		hm.clear();
	}
 
	public String getIp(int i) {
		return list.get(i).ip;
	}
	public int getNb(int i) {
		return list.get(i).nb;
	}
	public int getSize() {
		return (list == null ? 0 : list.size());
	}
 
}

**ChipsterJulien** · 07/01/2010, 17h19

La liste est toujours vide cependant je suis d'accord que c'est plus simple

**Rei Ichido** · 07/01/2010, 17h27

Oula, oui j'ai un peu zappé l'initialisation de la liste

:

Code :

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

1
2
3
4
5
6
7
 
 
	public void trie() {
		list = new ArrayList<SingleIP>(hm.values());
		Collections.sort(list);
		hm.clear();
	}

**ChipsterJulien** · 07/01/2010, 17h34

nop en fait c'est plutôt une erreur de frappe car plus haut tu as fait une initialisation de liste

Du cou en modifiant ça donne ça :

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
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class Ip {
 
	public class SingleIP implements Comparable<SingleIP> {
		private String ip;
		private Integer nb;
 
		public SingleIP(String ip) {
			this.ip = ip;
			this.nb = 1;
		}
 
		public int compareTo(SingleIP p_o) {
			return this.nb.compareTo(p_o.nb);
		}
	}
 
	private Map<String, SingleIP> hm = new HashMap<String, SingleIP>();
	private ArrayList<SingleIP> liste = null;
 
	public void addIp(String ip) {
		if(hm.containsKey(ip)) {
			SingleIP s_ip = hm.get(ip);
			++s_ip.nb;
		}
		else {
			hm.put(ip, new SingleIP(ip));
		}
	}
	public void trie() {
		liste = new ArrayList<SingleIP>(hm.values());
		Collections.sort(liste);
		Collections.reverse(liste);
		hm.clear();
	}
 
	public String getIp(int i) {
		return liste.get(i).ip;
	}
	public int getNb(int i) {
		return liste.get(i).nb;
	}
	public int getSize() {
		return (liste == null ? 0 : liste.size());
	}
}

**ChipsterJulien** · 07/01/2010, 17h40

Y a-t-il d'autres choses que je peux améliorer sur ce programme ou ça risque d'être difficile ?

**ChipsterJulien** · 07/01/2010, 18h38

En tout cas merci pour votre aide bien précieuse

[trie value de HashMap] Soucis de performances

Collection et Stream Java

Discussions similaires

Partager

Partager