Discussion :

[fanzyride]

Bonjour,
Juste pour un conseil sur un tri, en performance.

Donc pour faire simple, je suis en stage dans un laboratoire et je bosse sur une appli bizarrement codée. j'ai une classe qui "implements" une interface qui déclare une fonction sortByfreq.

En gros l'instance de ma classe, c'est une Liste de vecteur. Chaque vecteur contient un String et un vecteur d'occurrences de ce String dans un texte étudié.
Je dois trié cette liste en fonction des occurrences de chaque chaine par ordre croissant et je voudrais savoir quelle est la manière la plus performante ne prenant pas trop de mémoire qui pourrait traiter cela

Merci d'avance

[Pill_S]

Ce serait peut-être plus simple avec un ptit bout de code non? Parce que là je me représente pas très bien ton graph d'objets...

Tu as un truc comme ça?

Code :

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

1
2
 
List<Vector> list=...;

et dans chaque Vector, 2 entrées, la première est une string, la deuxième un Vector?

[fanzyride]

Non c'est l'instance de la classe qui est un vecteur, c'est pour ça qu'il n'y a pas vraiment de code à montrer.

mais ma classe est déclaré de la sorte :

Code :

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

public class SEGINCONTEXTSLIST extends SortableDataVector implements ClickableVector

tout cela "extends" une classe nommé DataVector qui elle "extends" Vector

J'espère m'être fait comprendre.
Merci

[Pill_S]

Ok... et les champs String et Vector ils sont comment?

donne-nous un peu plus de code stp

[fanzyride]

Ce vecteur contient des objects de cette classe :

Code :

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

public class SEGINCONTEXTS

qui elle, a pour attribut :

Code :

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

1
2
3
4
5
6
7
8
     /**
      * The String representation of the segment
      */
     private String segString;
     /**
      * The list of relative OffsetPairs for each occurence of the segment
      */
     private OffsetPairList occList;

OffsetPairList c'est mon vecteur d'occurrences.

[Pill_S]

Ok... alors un comparateur de ce genre devrait faire l'affaire:

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
 
Comparator<SEGINCONTEXTS> comparator = new Comparator<SEGINCONTEXTS>() {
            public int compare(SEGINCONTEXTS o1, SEGINCONTEXTS o2) {
                if((o1==null && o2==null) || o1==o2) {
                    return 0;                    
                }
 
                if(o1==null) {
                    return +1;
                }
                if(o2==null) {
                    return -1;
                }
 
                return o1.occList.size().compareTo(o2.occList.size());
            }
        };

et le tri:

Code :

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

1
2
3
4
5
6
 
// Conversion vers une liste pour faire le tri (tri impossible sur des vecteurs)
Vector<SEGINCONTEXTS> v = ...;
List l = Arrays.asList(v.toArray(new SEGINCONTEXTS[v.size()]));
Collections.sort(l, comparator);
// Maintenant, la liste 'l' est triée en fonction des critères définis dans le comparator

[Iyoiyo]

Poypoypoy... Je n'arrive pas trouver la source mais je croix me rappeler qu'il est important que la fonction compare retourne une valeur plus représentative de la différence entre deux objets. Pourtant :

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

Dixit la JavaDoc1.6. (MAIS DIFFERENTE DE LA JavaDoc1.3 !!)

Mais :

Note: The return value does not have to be -1, 0, or 1. Only the sign is important, not the value. In this case, the code just returns the difference in years, without worrying about the magnitude.

Dixit ce document

Et je n'arrive pas a trouver le lien sur une autre discution qui expliquai les optimisations algorithmiques dans l'API Java utilisant des valeurs autre que -1,0 et 1... Damned... On m'aurai mentis ?

[Pill_S]

Damned... On m'aurai mentis ?

probablement... y'a plein de légendes urbaines sur java (qui disent que c'est lent, etc.)

[fanzyride]

ça marche !
Juste un petit problème avec le compareTo, il lui faut des Integer, les Int il peut pas.
Merci Beaucoup

[Iyoiyo]

Problème d'autoboxing ?

Code :

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

return new Integer(o1.occList.size()).compareTo(new Integer(o2.occList.size()));

Facile quand même non ?

[Pill_S]

Juste un petit problème avec le compareTo, il lui faut des Integer, les Int il peut pas.

Oui, problème d'autoboxing. Vérifie que ton compilateur est bien en mode Java5+

Sinon, la solution Iyoiyo peut aussi fonctionner (juste remplacer new Integer par Integer.valueOf, afin d'optimiser).

[Iyoiyo]

Sinon, la solution Iyoiyo peut aussi fonctionner (juste remplacer new Integer par Integer.valueOf, afin d'optimiser).

+1