Comment est-ce que la classe TreeMap peut sauver votre journée ?

Située au sein de l’API collection de Java SE, la classe TreeMap se présente comme un tableau associatif (c’est-à-dire une Map) ordonné et navigable. Les éléments de cette collection sont répartis dans un arbre, facilitant la recherche d’un élément. L’un des intérêts de cette collection est qu’elle permet de répondre à la question : « Quel élément de ma collection est le plus proche par rapport à cet autre élément que je fournis ? »

Introduction

En tant qu’exemple, supposons que vous soyez en charge des réservations d’une salle. Voici quelques-unes de ces réservations :

• Du 4 janvier au 7 janvier : M. A
• Du 10 janvier au 21 janvier : Mme B
• Du 5 février au 18 février : M. A
• Du 20 février au 3 mars : M. C

Si une réservation ne peut pas en chevaucher une autre, comment créer une fonction permettant de déterminer l’occupant de la salle au 10 février ? Et au 19 février ?

Algorithmes possibles et performance

Il y a bien évidemment plusieurs manières de répondre à ces questions. Typiquement, dans l’une de ces réponses, on enregistre les réservations dans une collection, un Set ou une List par exemple. Lors de la recherche de l’occupant à une date donnée, la fonction parcourt l’ensemble des réservations en testant chaque élément. Il s’agit là de l’algorithme de recherche linéaire. Dans le pire des cas, sa complexité en temps est de O(n). Le pire cas apparaît lorsque vous avez à tester tous les éléments, ce qui arrive lorsque l’élément recherché est le dernier à être testé ou lorsque cet élément n’apparaît pas dans l’ensemble des éléments à tester.

Pour améliorer cela, vous pouvez aussi utiliser un algorithme de recherche agissant par dichotomie (binary search). Celui-ci consiste à diviser l’ensemble des éléments en deux sous-ensembles à chaque étape de la recherche et à continuer la recherche sur l’un de ces sous-ensembles. Pour fonctionner, cet algorithme nécessite que l’ensemble des éléments à tester soit ordonné. La complexité de cet algorithme est de O(log(n)) dans le pire des cas. L’algorithme par dichotomie est donc plus performant puisque si nous prenons un ensemble initial de 7 éléments, il vous faudra au maximum 3 tests pour trouver un élément (dans le pire des cas), contre 7 tests pour l’algorithme linéaire. De même, il vous faudra 10 tests au maximum sur 1000 éléments contre 1000 tests pour l’algorithme linéaire.

L’algorithme par dichotomie pourrait être intéressant, mais il subsiste un problème : cet algorithme a besoin d’un ensemble ordonné, ce qui n’est pas le cas de l’algorithme linéaire. Le fait d’ordonner un ensemble a un coût. Dans les classes java.util.Arrays et java.util.Collections, Java propose la méthode sort(). Si nous nous référons à la Javadoc de cette méthode, l’algorithme de tri utilisé par Java est le tri fusion (merge sort). Celui-ci garantit une complexité en temps de O(n.log(n)), ce qui est performant pour un algorithme de tri basé sur la comparaison. En reprenant l’exemple précédent, on s’aperçoit que le coût de l’application du tri fusion suivit de la recherche par dichotomie est supérieur au coût de la recherche linéaire, qui lui n’a pas besoin d’étape de tri.

Concernant la recherche par dichotomie, une autre approche consiste à générer l’arbre binaire (binary tree) correspondant. En effet, l’algorithme de recherche par dichotomie représente l’ensemble des éléments à tester comme un arbre virtuel à parcourir, sachant que cet arbre est binaire (2 fils par noeud) et équilibré (ie. la différence de profondeur entre deux branches ne dépasse pas 1). À chaque étape de l’algorithme, on choisit de parcourir le sous-ensemble à gauche (ou sous-arbre de gauche) ou le sous-ensemble à droite (ou sous-arbre de droite), que sépare un élément central (ou noeud) de l’ensemble (ou arbre) des éléments à tester. Maintenant, si vous utilisez une structure de données telle que l’arbre rouge-noir (red-black tree) pour représenter votre arbre binaire, vous avez les garanties suivantes :

• Chaque fois qu’un élément est ajouté, il est automatiquement trié par rapport au reste de l’arbre.
• Les opérations d’insertion et de recherche ont un coût en temps de O(log(n)) chacune.

L’insertion de données plus la recherche ont donc un coût de 2.O(log(n)). L’arbre rouge-noir est donc très performant vis-à-vis de la recherche linéaire. La classe TreeMap représente un arbre binaire équilibré et utilise la représentation arbre rouge-noir.

L’autre aspect intéressant est que la classe TreeMap propose les méthodes ceilingEntry() et floorEntry(). Ces deux méthodes permettent de retrouver l’entrée dans le TreeMap dont la clé est la plus proche respectivement supérieurement et inférieurement vis-à-vis de la clé passée en paramètre.

Représentation d’une réservation

Ci-dessous se trouve le code simplifié d’une classe représentant une réservation. Cette implémentation utilise Guava.

public class Reservation {
    public Date from;
    public Date to;
    public String occupant;

    public Reservation(Date from, Date to, String occupant) {
        this.from = from;
        this.to = to;
        this.occupant = occupant;
    }

    public boolean contains(Date date) {
        return !(from.after(date) || to.before(date));
    }

    @Override
    public String toString() {
        return Objects.toStringHelper(this)
                      .add("from", from)
                      .add("to", to)
                      .add("occupant", occupant)
                      .toString();
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(from, to, occupant);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof Reservation)) {
            return false;
        }
        Reservation reservation = (Reservation) obj;
        return Objects.equals(from, reservation.from)
               && Objects.equals(to, reservation.to)
               && Objects.equals(occupant, reservation.occupant);
    }
}

Nous retrouvons ci-dessous les quatre réservations présentées en introduction de cet article.

Date from, to;
Calendar calendar = Calendar.getInstance();

calendar.set(2011, 0, 4);
from = calendar.getTime();
calendar.set(2011, 0, 7);
to = calendar.getTime();
Reservation reserv1MrA = new Reservation(from, to, "M. A");

calendar.set(2011, 0, 10);
from = calendar.getTime();
calendar.set(2011, 0, 21);
to = calendar.getTime();
Reservation reserv1MrsB = new Reservation(from, to, "Mme B");

calendar.set(2011, 1, 5);
from = calendar.getTime();
calendar.set(2011, 1, 18);
to = calendar.getTime();
Reservation reserv2MrA = new Reservation(from, to, "M. A");

calendar.set(2011, 1, 20);
from = calendar.getTime();
calendar.set(2011, 2, 3);
to = calendar.getTime();
Reservation reserv1MrC = new Reservation(from, to, "M. C");

Comment retrouver une réservation à partir d’une date ?

Regroupons les réservations dans une classe que nous appellerons Planning. Une fois instanciée, vous pouvez y ajouter des réservations (méthode add()). Mais, vous pouvez aussi récupérer une réservation à une date donnée (méthode getReservationAt()).

Il y a deux étapes pour récupérer une réservation à une date donnée :

1. On utilise d’abord la méthode floorEntry() de la classe TreeMap. Cette méthode récupère l’Entry dont la clé représente la plus grande date inférieure ou égale à la date fournie en paramètre.
2. On vérifie ensuite si la réservation (qui correspond à la valeur de l’Entry récupéré) contient la date donnée en paramètre.

public class Planning {
    public final TreeMap<Date, Reservation> reservations;

    public Planning() {
        reservations = new TreeMap<Date, Reservation>();
    }

    public void add(Reservation reservation) {
        reservations.put(reservation.from, reservation);
    }

    public Reservation getReservationAt(Date date) {
        Entry<Date, Reservation> entry = reservations.floorEntry(date);
        if (entry == null) {
            return null;
        }
        Reservation reservation = entry.getValue();
        if (!reservation.contains(date)) {
            return null;
        }
        return reservation;
    }
}

Test

Pour la partie test, nous allons enregistrer les réservations que nous avons rencontrées en début d’article.

Planning planning = new Planning();
planning.add(reserv1MrA);
planning.add(reserv1MrsB);
planning.add(reserv2MrA);
planning.add(reserv1MrC);

Maintenant, voyons comment obtenir les personnes qui ont effectué une réservation le 10 février et le 19 février ? (Les assertions proviennent de l’API FEST-assert)

Calendar calendar = Calendar.getInstance();

calendar.set(2011, 1, 10);
Date dateOfMrA = calendar.getTime();
assertThat(planning.getReservationAt(dateOfMrA).occupant).isEqualTo("M. A");

calendar.set(2011, 1, 19);
Date dateNoReservation = calendar.getTime();
assertThat(planning.getReservationAt(dateNoReservation)).isNull();

Cet article est une traduction libre, faite avec l’autorisation de l’auteur, de « How TreeMap can save your day? » publié par François Sarradin le 20/05/2011 sur http://kerflyn.wordpress.com/.

Notes sur la traduction

Par rapport à ce qui est écrit ci-dessus, la structure TreeMap suffit dans le cadre d’une application mono-thread. Dans une application multi-thread, cette structure de données présente des incohérences en terme de comportement, car elle ne supporte pas les accès asynchrones. Une solution pour résoudre ce problème consiste à utiliser sa version synchronized en passant par la méthode Collections.synchronizedSortedMap(). Cependant, cette solution présente deux inconvénients. Premièrement, les opérations sont synchrones au niveau de l’instance entière de la structure de données et l’appel à une opération bloque du coup toute la structure. Deuxièmement, l’objet récupéré n’est plus un NavigableMap et on ne peut plus bénéficier des méthodes ceilingEntry() et floorEntry(). Une autre solution passe par l’utilisation d’une skip-list. Cette structure est utilisée dans la classe ConcurrentSkipListMap qui possède les mêmes interfaces que la classe TreeMap. Elle a une complexité en log(n) en moyenne pour l’ensemble des opérations de base (insertion, recherche et suppression). Mais elle permet surtout l’utilisation de ces opérations de manière asynchrone.