août
2014
Un article de adiGuba
La méthode static Collections.sort() permet de trier les éléments d’une List.
Lorsqu’on y regarde de plus près son implémentation peut surprendre :
public static void sort(List list, Comparator c) {
Object[] a = list.toArray();
Arrays.sort(a, (Comparator)c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T) a[j]);
}
}
On peut en effet découper cela en trois partie :
- On crée un tableau temporaire d’Object à partir des éléments de la liste.
- On tri ce tableau via la méthode Arrays.sort() (qui effectue directement le tri sur les données du tableau).
- On redéfini chaque élément de la liste à partir des données triées du tableau, via un ListIterator.
Le fait de passer par un tableau temporaire et de réaffecter le résultat dans la liste peut sembler curieux et contre-performant…
On pourrait être tenté de faire un tri en modifiant directement les valeurs de la liste via leurs index et les méthodes get()/set().
Mais en fait cela poserait deux principaux problèmes :
- La performance du tri dépendrait alors de la complexité de ces méthodes, qui peut énormément varier selon l’implémentation de la liste.
C’est très performant sur une ArrayList, alors que c’est (vraiment) très coûteux sur une LinkedList où l’accès à un élément par index implique le parcours des éléments précédents…
Du coup une telle implémentation basé sur les index serait très performante sur une ArrayList, mais véritablement calamiteuse sur une LinkedList… - En manipulant directement les index, on ne peut pas détecter une modification concurrente qui serait effectuée pendant notre tri, rendant le résultat totalement incohérent.
Or l’API de Collection a une approche fail-fast qui a pour objectif de générer une exception au plus tôt pour éviter les incohérences (et c’est le cas lorsqu’on parcours via un itérateur).
Collections.sort() possède donc le meilleur compromis pour la majorité des listes, et on ne peut pas faire mieux sans connaitre plus précisément l’implémentation exacte de la liste…
Les méthodes par défaut de Java 8 changent la donne
Java 8 a introduit la notion de méthodes par défaut, ce qui permet d’étendre les interfaces avec des méthodes dont on fournirait une implémentation par défaut, et qui sera utilisée lorsque la méthode n’est pas implémentée par la classe fille.
L’API de Collections en a bien profité de cette fonctionnalité en s’enrichissant de plusieurs méthodes, dont une méthode sort() dans l’interface List<E>, déclarée de la manière suivante :
Collections.sort(this, c);
}
Cela permet d’enrichir l’API des interfaces, pour une utilisation plus naturelle.
On peut donc désormais trier une liste directement via la méthode sort() :
Collections.sort(list, comparator);
// avec Java 8 on peut désormais faire cela :
list.sort(comparator);
Mais ce n’est pas tout. La force des méthodes par défaut, c’est qu’il s’agit de vrai méthode virtuelle, qu’il est possible de redéfinir dans les classes implémentant l’interface.
C’est le cas par exemple de la classe ArrayList, qui effectue le tri directement sur son tableau interne :
@SuppressWarnings("unchecked")
public void sort(Comparator c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
Du coup list.sort() permet non seulement une utilisation plus simple, mais également potentiellement plus performante en permettant à chaque implémentation de List de fournir une version plus adaptée…
Collections.sort() fait de la résistance
On s’est alors retrouvé avec un nouveau problème, car contrairement à ce qu’on pourrait penser de prime abord, les méthodes Collections.sort() et list.sort() ne sont pas vraiment équivalente.
En effet si cette dernière peut profiter d’une implémentation spécifique de la méthode sort(), ce n’est pas le cas de Collections.sort() qui effectuera toujours le tri « standard » sans profiter d’une éventuelle implémentation spécifique de la liste qu’elle reçoit en paramètre :
Collections.sort(list, comparator);
// Tri d'une liste avec l'implémentation spécifique de l'instance (s'il y en a une)
// ou avec l'implémentation "standard" le cas échéant :
list.sort(comparator);
Or l’écosystème Java est énorme… mais loin d’avoir déjà migré sur Java 8.
De nombreux codes ou librairies utilisent Collections.sort(), et ils ne profitent donc pas des implémentations spécifiques de sort().
Ainsi la grande majorité des codes et librairies Java ne profitaient pas de l’implémentation de sort() optimisé pour les ArrayList, ni pour toute autre type de liste qui proposerait une meilleure implémentation de sort()…
L’update 20 à la rescousse
La situation a toutefois été revue dans l’update 20 de Java 8, qui a inversé le fonctionnement de Collections.sort() et list.sort().
Ainsi Collections.sort() se contente désormais d’appeler list.sort() :
list.sort(c);
}
Et c’est le code de la méthode par défaut de l’interface List qui se charge désormais d’appliquer le tri de base :
default void sort(Comparator c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
De ce fait, l’utilisation des méthodes Collections.sort(list) ou list.sort() sont désormais équivalente :
- Si l’implémentation de la liste dispose d’une implémentation spécifique de sort(), elle sera utilisée.
- Sinon on utilisera la méthode par défaut, basé sur la copie dans un tableau (bref le meilleur compromis lorsqu’on ne connait pas l’implémentation).
3 Commentaires + Ajouter un commentaire
Tutoriels
Discussions
- [REFLEXION] Connaitre toutes les classes qui implémentent une interface
- Classes, méthodes private
- Recuperation du nom des parametres
- jre 1.5, tomcat 6.0 et multi processeurs
- L'apparition du mot-clé const est-il prévu dans une version à venir du JDK?
- Définition exacte de @Override
- [ fuite ] memoire
- Possibilité d'accéder au type générique en runtime
- Difference de performances Unix/Windows d'un programme?
Super tour d’horizon…
L’update 20 corrige un sacré trou dans la raquette du jdk… .
a+
Philippe
Salut,
J’ai bien aimé ton article.
Les fonctions par défaut, ce sont des fonctions implémentées directement dans l’interface?
Oui c’est une des nouveautés de Java 8.
Cela permet d’étendre les interfaces sans tout casser !
a++