IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Java Discussion :

Tri de structure


Sujet :

Langage Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Inscrit en
    Juillet 2007
    Messages
    456
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 456
    Par défaut Tri de structure
    Salut à tous,

    Je voudrais avoir votre avis concernant un tri que je fais.

    J'ai une List qui contient pour le moment 16200 items (elle peut monter jusqu'a 100 000 ou bien plus). Pour la trier j'utilise le sort de Collections :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Collections.sort(dataList, comparatorTable.get(columnSorted) );
    Et je lui passe en parametre mon comparator, qui dans le cas par défaut est :
    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
    public class TimeCreationComparator extends BeanComparator{
     
     
    	public int compare(OrderGroupRecordBean o1, OrderGroupRecordBean o2) {
     
    		try {
     
     
    			SimpleDateFormat format = new SimpleDateFormat("yyyyMMdd-HH:mm:ss.SSS");
    			Date date1 = format.parse(o1.getOrderTimecreation());
    			Date date2 = format.parse(o2.getOrderTimecreation());
     
    			if ( ascending )
    			{
    				if ( date1.getTime() < date2.getTime() )
    					return -1;
    				else if ( date1.getTime() > date2.getTime() )
    					return 1;
    				else
    					return 0;
    			}
    			else 
    			{
    				if ( date1.getTime() < date2.getTime() )
    					return 1;
    				else if ( date1.getTime() > date2.getTime() )
    					return -1;
    				else
    					return 0;
    			}
    		} catch (ParseException e) {
    			e.printStackTrace();
    		}
    		return 0;
    	}
    Le problème c'est qu'avec cette méthode, pour 16200 items prend 62s ce qui est énorme par rapport à l'application que je développe, le temps de réponse doit être de l'ordre de quelques milisecondes ...

    A votre avis c'est normale que ça prend tant de temps ? Et ce que vous avez une méthode meilleure que je pourrais utiliser, sans avoir à développer un nouveau quicksort biensur


    Merci bq

  2. #2
    Membre éclairé
    Profil pro
    Inscrit en
    Juin 2005
    Messages
    731
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2005
    Messages : 731
    Par défaut
    Bonjour,
    je prendrais le problème à l'envers et j'utiliserai un genre de SortedList pour que le tri soit effectué lors de l'ajout d'un élément dans ma collection.
    Ensuite, à voir si c'est possible dans ton process.

  3. #3
    Membre éclairé
    Inscrit en
    Juillet 2007
    Messages
    456
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 456
    Par défaut
    Le probleme c'est que j'ai plus de 20 comparateurs que l'utilisateur peut choisir à sa guise.
    Du coup avant l'ajout, peut etre que c'est le comparateur 1 qui est utilisé et juste avant l'ajout (l'ajout est automatique, c'est par rapport à la reception d'un événement exterieur ) il change de comparator. Du coup je dois retrier toutes mes données selon le nouveau comparateur.

    Je sais pas si j'etais clair dans mon explication

    Merci

  4. #4
    Expert éminent
    Avatar de adiGuba
    Homme Profil pro
    Développeur Java/Web
    Inscrit en
    Avril 2002
    Messages
    13 938
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java/Web
    Secteur : Transports

    Informations forums :
    Inscription : Avril 2002
    Messages : 13 938
    Billets dans le blog
    1
    Par défaut
    Salut,



    C'est pour cela que les dates ne doivent pas être stocké sous forme de String : cela ne facilite pas les traitements (et sans compter l'occupation mémoire) !!! S'il y a un objet Date ce n'est pas pour rien !



    Et en plus de cela il y a beaucoup à dire sur ton implémentation de compareTo() :
    • Le SimpleDateFormat devrait être une variable d'instance, afin d'éviter de la recréer à chaque comparaison, ce qui peut s'avérer assez lourd.
    • Plutôt que de faire des comparaisons peu lisible, tu pourrais directement utiliser la méthode compareTo() de la classe Date.
    • Ton printStackTrace() est peu convaincant : si l'exception ne doit pas arriver il faut mieux la remonter comme une RuntimeException, cela permet de déceler plus vite le problème s'il survient, plutôt que de retourner une valeur bidon qui va laisser le programme continuer et potentiellement engendré d'autres problèmes...


    Bref cela donnerait quelque chose du genre :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    	private final SimpleDateFormat format = new SimpleDateFormat("yyyyMMdd-HH:mm:ss.SSS");
     
    	public int compare(OrderGroupRecordBean o1, OrderGroupRecordBean o2) {
    		try {
    			Date date1 = format.parse(o1.getOrderTimecreation());
    			Date date2 = format.parse(o2.getOrderTimecreation());
    			return (ascending ? 1 : -1) * date1.compareTo(date2);
    		} catch (ParseException e) {
    			// Cela ne devrait pas arriver !
    			throw new RuntimeException(e);
    		}
    	}
    Et le traitement de 16200 éléments prend environ 2.3 secondes contre 36 avec ton code...



    A la rigueur, puis tes dates sont dans un format inversé (année->mois->jour->heure...), on pourrait faire une comparaison par ordre alphabétique, ce qui donnerait tout simplement ceci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    	public int compare(OrderGroupRecordBean o1, OrderGroupRecordBean o2) {
    		return (ascending ? 1 : -1) * o1.getOrderTimecreation().compareTo(o2.getOrderTimecreation());
    	}
    On est déjà bien plus rapide (environ 125ms).




    Mais le mieux serait vraiment de stocker les dates dans des Dates !
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    	public int compare(OrderGroupRecordBean o1, OrderGroupRecordBean o2) {
    		return (ascending ? 1 : -1) * o1.getTime().compareTo(o2.getTime());
    	}
    Et ce serait surtout encore plus rapide : moins de 15 millisecondes !!


    a++

  5. #5
    Membre éclairé
    Inscrit en
    Juillet 2007
    Messages
    456
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 456
    Par défaut
    Merci bq adiGuba,

    Je reconnais que mon comparateur laisse à désirer, mais je croyais pas qu'il pourrait à ce point l'origine du problème

    En tous merci bq, j'essayerai d'implémenter tous cela et je vous tiens au courant.

  6. #6
    Expert éminent
    Avatar de adiGuba
    Homme Profil pro
    Développeur Java/Web
    Inscrit en
    Avril 2002
    Messages
    13 938
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java/Web
    Secteur : Transports

    Informations forums :
    Inscription : Avril 2002
    Messages : 13 938
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Esil2008 Voir le message
    Je reconnais que mon comparateur laisse à désirer, mais je croyais pas qu'il pourrait à ce point l'origine du problème
    Tu as ici affaire à un point sensible, puisque le comparateur sera utilisé pour comparer les divers éléments de ta liste. De ce fait il sera appelé un très grand nombre de fois.

    Du coup la moindre petite "lourdeur" prend une ampleur énorme !

    a++

  7. #7
    Membre éclairé
    Inscrit en
    Juillet 2007
    Messages
    456
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 456
    Par défaut
    Je me suis contenté de comparaitre les string pour l'instant et ca marche tres bien. Je passerai au date après, car c vrai que c'est plus interessent de comparaitre des dates.

    Merci encore

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [XSLT] Gros souci de tri sur structure arborescente
    Par stujava dans le forum XSL/XSLT/XPATH
    Réponses: 1
    Dernier message: 25/03/2010, 17h49
  2. tri champ structure en c
    Par laureat dans le forum Débuter
    Réponses: 9
    Dernier message: 31/08/2009, 11h10
  3. [VB6]Tri multi-colonnes sur tableau de structure
    Par ELGUEVEL dans le forum VB 6 et antérieur
    Réponses: 2
    Dernier message: 17/02/2006, 08h02
  4. Réponses: 9
    Dernier message: 13/02/2006, 08h39
  5. tri par insertion et Structures
    Par bonjour69 dans le forum C
    Réponses: 2
    Dernier message: 23/12/2005, 12h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo