[1.5] Tri d'une Map

**Arnaud F.** · 25/05/2007, 00h23

Bonsoir à toutes et à tous,

dans le cadre d'un projet, je dois compter le nombre d'occurences de chaque caractères dans un texte, et pour ça, j'ai utilisé la méthode donnée par adi Guba qui fonctionne très bien.

Seulement à la place d'Integer comme valeur j'ai une classe Symbole définie comme suis :

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
public class Symbole
{
	private Integer freq;
	private double proba;
	private double a;
	private String code;
 
	public Symbole()
	{
		freq= 1;
		proba= 0.0;
		a=  0.0;
		code= "";
	}
 
	public int getFreq() { return freq; }
	public double getProba() { return proba; }
	public double getA() { return a; }
	public String getCode() { return code; }
 
	public void incrementFreq() { freq++; }
	public void setProba(double p) { proba= p; }
	public void setA(double aa) { a= aa; }
	public void setCode(String c) { code= c; }
 
	public String toString() { return new String("Fréquence : " + freq + " ; Probabilité : " + proba + " ; A : " + a + " Code : "  + code); }
}

Et j'aimerai pouvoir trier ma Map selon le critère proba. Possible ou dois-je changer d'implentation?

**remika** · 25/05/2007, 00h39

Si tu as une Map triée j'imagine que c'est une TreeMap.
Tu peux par exemple utiliser une classe héritant de Comparator<Symbole> et l'utiliser dans le constructeur de ta TreeMap.

**Arnaud F.** · 25/05/2007, 00h44

Pourrais-tu me donner un exemple de code pour voir de quoi il retourne et de comment l'implémenter?

d'avance

**sinok** · 25/05/2007, 01h18

Les maps sont des collections donc
http://java.developpez.com/faq/java/...rierCollection

**Arnaud F.** · 25/05/2007, 09h52

Merci sinok

Voici donc ma nouvelle classe Symbole :

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
public class Symbole implements Comparable
{
	protected Integer freq;
	protected double proba;
	protected double a;
	protected String code;
 
	public Symbole()
	{
		freq= 1;
		proba= 0.0;
		a=  0.0;
		code= "";
	}
 
	public int getFreq() { return freq; }
	public double getProba() { return proba; }
	public double getA() { return a; }
	public String getCode() { return code; }
 
	public void incrementFreq() { freq++; }
	public void setProba(double p) { proba= p; }
	public void setA(double aa) { a= aa; }
	public void setCode(String c) { code= c; }
 
	public String toString() { return new String("Fréquence : " + freq + " ; Probabilité : " + proba + " ; A : " + a + " ; Code : "  + code); }
 
	public int compareTo(Object s)
	{
		int res= -1;
		Symbole tmp;
		if(s instanceof Symbole)
		{
			tmp= (Symbole) s;
			if(this.getProba() > tmp.getProba())
				res= 1;
		}
		return res; 
	}
}

Seulement, la méthode sort utilisée pour trier les collections ne semble que trier les List et non les Map , autant dire que je suis perdu

**remika** · 25/05/2007, 11h03

Si tu fais simplement une TreeMap<Symbole>, comme tu as "implémenté Comparable", ta Map sera triée selon l'ordre que tu veux :

Code :

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

1
2
3
4
5
6
 
Map<Symbole,Integer> map = new TreeMap<Symbole,Integer>();
map.put(new Symbole(0.98),25);
map.put(new Symbole(0.22),23);
map.put(new Symbole(0.43),23);
System.out.println(map);

avec ta classe Symbole à peine modifié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
53
54
55
56
57
58
59
60
61
62
 
public class Symbole implements Comparable<Symbole> { 
    protected Integer freq;
    protected double proba;
    protected double a;
    protected String code;
 
    public Symbole()  {
        freq= 1;
        proba= 0.0;
        a= 0.0;
        code= "";
    }  
 
    public Symbole(double proba)  {
        freq= 1;
        this.proba = proba;
        a= 0.0;
        code= "";
    }  
 
    public int getFreq() {
        return freq;
    }
 
    public double getProba() {
        return proba;
    } 
 
    public double getA() {
        return a;
    } 
 
    public String getCode() {
        return code;
    }
 
    public void incrementFreq() {
        freq++;
    }  
 
    public void setProba(double p) {
        proba= p;
    }
 
    public void setA(double aa) {
        a= aa;
    }  
 
    public void setCode(String c) {
        code= c;
     }
 
    public String toString() {
        return new String("Fréquence : " + freq + " ; Probabilité : " + proba + " ; A : " + a + " ; Code : " + code);
    }
 
    public int compareTo(Symbole s)  {
        if(this.getProba() > s.getProba())  return 1;
        return -1;
    }
}

**Arnaud F.** · 25/05/2007, 11h06

Y a un léger souci avec ta méthode, c'est que je n'ai plus le caractère associé au symbole... Y représente quoi ton Integer dans le champs des valeurs?
Qui plus est, la liste des symboles n'est pas unique et peut contenir des valeurs nulles...

Ex: Pour deux caractères, on aura :
<{1, 0.5, null, null} , a>
<{1, 0.5, null, null} , b>

**remika** · 25/05/2007, 11h10

Y a un léger souci avec ta méthode, c'est que je n'ai plus le caractère associé au symbole

Explique mieux, là je ne comprends pas.

je dois compter le nombre d'occurences de chaque caractères

Ba l'Integer c'est le nombre d'occurences.

**Arnaud F.** · 25/05/2007, 11h26

Bon, je vais réexpliquer ce que je cherche à faire...

A la base, j'ai un texte, de ce texte, je compte pour chaque caractères, le nombre de fois ou il apparait, sa probabilité d'apparition etc. (cf classe Symbole).
Pour faire cette opération, je me suis inspiré de ce post .

Seulement j'aimerai pouvoir trier ceci non pas par clé mais par valeurs...

Donc si je faut que je change d'implémentation, il faut aussi que je change la manière dont je compte les caractères...

Il me faut l'association Character<->Symbole pour retrouver mes petits.

J'espère avoir été plus clair

**adiGuba** · 25/05/2007, 11h32

Salut,

Envoyé par remika

Si tu fais simplement une TreeMap<Symbole>, comme tu as "implémenté Comparable", ta Map sera triée selon l'ordre que tu veux :

Attention : la clef d'une Map doit implémenter correctement les méthodes hashCode() et equals() qui permettent de retrouver l'objet plus rapidement.

De plus les valeurs renvoyé par ces méthodes ne doivent pas varier : si un objet est modifié il est fort possible qu'il ne puisse pas être retrouvé par la suite (ceci est du à l'algorithme de recherche des Map).

Envoyé par remika

Ba l'Integer c'est le nombre d'occurences.

Si j'ai bien compris c'est la classe Symbole qui remplace le nombre d'occurrences...

@buchs : as-tu besoin d'une association qui soit trié en permanence ?
Dans ce cas il va falloir que tu te crées un type de collection mixte contenant une Map (pour l'association Character->Symbole) et une List (pour le coté ordonné).

Sinon, si tu as juste besoin d'avoir les Symbole trié à la fin du traitement, il te suffit de "transformer" ta Map en List :

Code :

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

1
2
	List<Symbole> list = new ArrayList<Symbole>(map.values());
	Collections.sort(list);

a++

**Arnaud F.** · 25/05/2007, 11h43

adi Guba

En fait, si je pourrai trier la Map à la fin du traitement ( c'est-à-dire une fois les occurences de chaque caractères comptées, bref la Map rempli après occurences ).

Pour l'instant, j'ai fais 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
public Map<Character, Symbole> trierMap(Map<Character, Symbole> map)
{
	Map<Character, Symbole> res= new TreeMap<Character, Symbole>();
	List<Symbole> list= new ArrayList<Symbole>();
	list.addAll(map.values());
	Collections.sort(list, new Comparator<Symbole>()
	{
		public int compare(Symbole s0, Symbole s1) { return s1.getFreq() - s0.getFreq(); }
	});
 
	Object car;
	Symbole s_tmp;
 
	for(Symbole s: list)
	{
		Collection cle= map.keySet();
		Iterator i_cle= cle.iterator();
		while(i_cle.hasNext())
		{
			car= i_cle.next();
			s_tmp= map.get(car);
			if(s.equals(s_tmp))
				res.put((Character)car, s);
		}
	}
	return res;
}

Le tri fonctionne dans le sens ou au moment ou j'insère, le tri par probabilité est fait, seulement, lors du renvoi, vu que c'est une TreeMap, res est de nouveau triée par clé et non plus par la fréquence d'apparition ( ou proba, de tte facon les deux sont proportionnels

)

[edit] J'ai relu ton post, en gros oui, elle doit être triée en permanence

**Arnaud F.** · 25/05/2007, 15h49

Re,

J'ai testé d'utiliser des List<Object> à la place de la Map en mettant un caractère puis un symbole et en recastant le tout, mais ce n'est pas trop gérable voir ingérable.

Donc si vous avez des idées n'hésitez pas

++

**Arnaud F.** · 27/05/2007, 14h39

Envoyé par adiGuba

@buchs : as-tu besoin d'une association qui soit trié en permanence ?
Dans ce cas il va falloir que tu te crées un type de collection mixte contenant une Map (pour l'association Character->Symbole) et une List (pour le coté ordonné).

adiGuba, pourrait-tu m'expliquer comment faire ça? J'ai passé 2 jours à essayer avec les List et autres mais ça ne donne vraiment rien de bien

Je vois pas le bout de ce tri, et tant que je l'ai pas fait, je peux pas continuer

**djo.mos** · 27/05/2007, 14h58

Bonjour.
Ca fait deux jours que je vois ce post, et je dois avouer que je n'arrive pas à comprendre comment à ce qu'on veut trier un Map ! Ca n'a aucun sens pour moi, alors corrigez moi si je me trompe SVP !
Je m'explique : on peut pas parcourir un Map linéairement, comme pour une liste, on accède plutôt à ces éléments par clé. L'ensemble de ces clés est un Set ==> pas de notion de trie ! Et l'ensemble des valeurs est à priori une Collection et donc triable, mais en pratique, c'est l'implémentation du Map qui le gère, donc même si on agit sur lui (en le triant), rien n'empêche l'implémentation de le toucher.

Je le répète, corrigez moi si je me trompe SVP !

Comme solution à ton problème, je te propose d'agir autrement. A l'origine, tu voulais trier le Map (incensé à mes yeux), mais je peux te propose deux autres solutions :

- Soit tu transformes ton map en une liste de Symboles à la fin du traitement, et comme Symbole implémente Comparable (dans une des propositions précédentes) tu peux trier cette liste par proba ! Mais là tu perds les avantages du Map (accès direct par clé)

- Soit tu crées une classe SymboleComparator qui implémente Comparator, et tu fournis une méthode qui prend le KeySet du Map et qui retourne une liste de Character triée selon la proba. Ensuite, pour parcourir ton Map, tu utilises cette liste et comme ça, t'auras tes Symbole dans l'ordre !

Je préfère la seconde solution, et si ça t'interesse (et que je ne suis pas parti en sucette), je peux te fournir plus de détails la concernant.

**Arnaud F.** · 27/05/2007, 15h34

Je suis tout à fait d'accord avec toi, mais en fait si j'utilise la Map c'est surtout pour garder la correspondance entre Character et Symbole quoi! J'ai pas dis que c'était le meilleur choix, juste pris ça parce que c'était proposé dans une méthode tirée d'un post pour compter les caractères...

Ta première méthode, je l'ai déjà faite, seulement il me faut la correspondance en continu...

Sinon ta seconde méthode à l'air intéressante

Envoyé par Modjo

Je préfère la seconde solution, et si ça t'interesse (et que je ne suis pas parti en sucette), je peux te fournir plus de détails la concernant.

Oui ça m'intéresse,

**djo.mos** · 27/05/2007, 15h51

Allons y.
Juste une petite rectification, plutôt que faire que Symbole implémente Comparable, on va créer un Comparator :

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
 
public class SymboleComparator implements Comparator {
    private Map<Character, Symbole> symbols;
 
    public SymboleComparator (Map<Character, Symbole> symbols){
        this.symbols = symbols;
    }
 
    public int compare(Object arg0, Object arg1) {
       double proba0 = symbols.get((Character)arg0);
       double proba1 = symbols.get((Character)arg1);
       return (proba0-proba1);
    }
 
}

La méthode qui transforme le keySet du MAp en une liste ordonné mais selon les probas :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
public class Utils {
public static List<Character> getSortedKeySet(Map<Character,
                                        Symbole> symbols){
 
  return Collections.sort(
                   new ArrayList<Character>(symbols),
                   new SymboleComparator(symbols)
            );
}
}

à la fin, quand tu veux parcourir ton map dans l'ordre, tu fais :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
Map<Character, Symbole> symbols;
:
:
:
List<Character> keys =Utils.getSortedKeySet(symbols);
for(Character c : keys){
  Symbole s = symbols.get(c);
  :
  :
}

Voilà, ça doit résoudre ton problème (à moins que je n'ai fait une petit erreur de frappe, mais l'idée est là)

Cordialement.

**Arnaud F.** · 27/05/2007, 16h04

Envoyé par Modjo

Allons y.
Juste une petite rectification, plutôt que faire que Symbole implémente Comparable, on va créer un Comparator :

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
 
public class SymboleComparator implements Comparator {
    private Map<Character, Symbole> symbols;
 
    public SymboleComparator (Map<Character, Symbole> symbols){
        this.symbols = symbols;
    }
 
    public int compare(Object arg0, Object arg1) {
       double proba0 = symbols.get((Character)arg0);
       double proba1 = symbols.get((Character)arg1);
       return (proba0-proba1);
    }
 
}

J'ai dû modifier la méthode compare tel quel :

Code :

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

1
2
3
4
5
    public int compare(Object arg0, Object arg1) {
       double proba0 = ((Symbole)symbols.get((Character)arg0)).getProba();
       double proba1 = ((Symbole)symbols.get((Character)arg1)).getProba();
       return (int)(proba0-proba1);
    }

Envoyé par Modjo

La méthode qui transforme le keySet du MAp en une liste ordonné mais selon les probas :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
public class Utils {
public static List<Character> getSortedKeySet(Map<Character,
                                        Symbole> symbols){
 
  return Collections.sort(
                   new ArrayList<Character>(symbols),
                   new SymboleComparator(symbols)
            );
}
}

Ne fonctionne pas (je code avec Eclipse) :

Impossible de retourner un résultat void

Le constructeur ArrayList<Character>(Map<Character,Symbole>) n'est pas défini

Donc la suite, je ne l'ai pas encore testée, je tente de résoudre ces deux erreurs déjà

++

**djo.mos** · 27/05/2007, 16h14

oops ! pardon, c'est plutôt :

Code :

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

1
2
3
4
5
6
7
8
9
10
public class Utils {
public static List<Character> getSortedKeySet(Map<Character,
                                        Symbole> symbols){
 
  return Collections.sort(
                   new ArrayList<Character>(symbols.keySet()),
                   new SymboleComparator(symbols)
            );
}
}

je manque de sommeil !

Autre chose, je pense pas que le casting

return (int)(proba0-proba1);

ferait l'affaire ! proba0-prob1 tjs dans [-1, 1] => (int)(proba0-proba1) tjs == 0 !

Il serait plus judicieux de faire :

Code :

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

1
2
3
4
5
6
7
8
9
10
public int compare(Object arg0, Object arg1) {
       double proba0 = symbols.get((Character)arg0);
       double proba1 = symbols.get((Character)arg1);
       if (proba0-proba1)<0
          return -1;
       else if (proba0-proba1)>0
          return 1;
       else return 0;
    }

En voulant faire un raccourci, on a failli tout bousiller !

**Arnaud F.** · 27/05/2007, 16h21

pour la correction du cast, c'est corrigé, par contre, j'ai toujours le souci du void...

Je viens de regarder la doc, et, en effet, la méthode sort est de type void, j'ai corrigé en :

Code :

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

1
2
3
4
5
6
7
public class Utils {
    public static List<Character> getSortedKeySet(Map<Character, Symbole> symbols){
        List<Character> list= new ArrayList<Character> (symbols.keySet());
            Collections.sort(list, new SymboleComparator(symbols));
        return list;
    }
}

J'ai plus que des Warnings sur les sécurités de type...

[edit] Au passage, lors du test pour le comparateur, ta mal mis les opérateurs de comparaison, tu manque vraiment de sommeil