[1.5] Tri d'une Map

Version imprimable

Voir 40 message(s) de cette discussion en une page

[1.5] Tri d'une Map

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:

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?

:merci:

24/05/2007, 23h39
remika

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.
24/05/2007, 23h44
Arnaud F.

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

:merci: d'avance :)
25/05/2007, 00h18
sinok

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

Merci sinok ;)

Voici donc ma nouvelle classe Symbole :

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

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:

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:

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;
    }
}

25/05/2007, 10h06
Arnaud F.

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

:merci:

Ex: Pour deux caractères, on aura :
<{1, 0.5, null, null} , a>
<{1, 0.5, null, null} , b>
25/05/2007, 10h10
remika

Citation:

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.

Citation:

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

Ba l'Integer c'est le nombre d'occurences.
25/05/2007, 10h26
Arnaud F.

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 :?
25/05/2007, 10h32
adiGuba
Salut,

Citation:

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

Citation:

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:

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

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

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

25/05/2007, 14h49
Arnaud F.

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

++
27/05/2007, 13h39
Arnaud F.

Citation:

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

:merci:
27/05/2007, 13h58
djo.mos

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.
27/05/2007, 14h34
Arnaud F.

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

Citation:

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

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

Code:

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:

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:

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.

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

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:

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); }
Citation:
Envoyé par Modjo
La méthode qui transforme le keySet du MAp en une liste ordonné mais selon les probas :
Code:

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

++

oops ! pardon, c'est plutôt :
Code:

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

Citation:

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:

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 !

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

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

27/05/2007, 15h31
djo.mos

Citation:

Envoyé par buchs

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

C'est tout à fait vrai, d'ailleurs je vais le faire tout de suite ! :king:

pour les warnings, tu peux t'en débarraser en ajoutant l'annotation suivante sur les méthodes qui les génèrent :

Code:

@SuppressWarnings("unchecked")

Sinon, du coté fonctionnel, ça résout tes problèmes ?

Voir 40 message(s) de cette discussion en une page

Fuseau horaire GMT +2. Il est actuellement 15h00.