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:

---

Collections.sort(dataList, comparatorTable.get(columnSorted) );

---

Et je lui passe en parametre mon comparator, qui dans le cas par défaut est :

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

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

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.

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

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:

---

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:

---

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:

---

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

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

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

Citation:

---

Envoyé par Esil2008

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

---

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

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