Skip-lists

École polytechnique, cours INF321, X2007, examen sur machine du 10 juin 2008. Sujet proposé par David Monniaux, avec remarques par Anne Canteaut et Olivier Delande.

Introduction

Motivation

On veut une structure de données capable de représenter une table de couples (clef, valeur), c'est-à-dire une fonction partielle associant une valeur à chaque clef pour un ensemble fini de clefs. La notation ab signifie que l'on associe la valeur b à la clef a.

Par souci de simplicité, nous traiterons ici le cas où les clefs sont des double et les valeurs des String (nous n'opérerons pas sur les valeurs sinon pour les faire afficher). En fait, tout ce que nous verrons se généralise à tout type de clef pourvu qu'on ait sur elles une relation d'ordre total et calculable (bref, qu'on puisse tester si k1<k2, k1=k2 ou k1>k2 étant données deux clefs k1 et k2).

On veut pouvoir insérer, modifier et supprimer ces associations clefvaleur.

La première méthode à laquelle on peut penser est la liste d'association : on crée une liste simplement chaînée de couples (clef, valeur), classée par ordre croissant des clefs. Si l'on cherche une clef prise au hasard, il faut en moyenne parcourir n/2 nœuds de la liste où n est le nombre d'éléments de la liste. Ceci veut dire que si l'on procède à n ajouts, le temps de calcul sera proportionnel à . Si l'on compte gérer de grosses bases de données, ce coût est prohibitif.

On désire donc utiliser une structure de données au temps d'accès proportionnel à log n en moyenne, ce qui garantira que le coût d'ajout de n éléments soit en n log n. Il en existe plusieurs (dont par exemple arbres binaires équilibrés). Nous avons choisi ici les skip lists (ou listes à enjambement), dont le temps d'accès est de log n en moyenne.

Nous implémenterons d'abord les listes d'association, puis les skip-lists.

Définitions

Une liste d'association est une suite de nœuds contenant chacun un couple (clef, valeur), chacun pointant sur le suivant, et le dernier pointant sur null. Les clefs de ces nœuds sont classées par ordre croissant. Ainsi, la liste d'association {3⟼lapin, 0⟼Toto, 1⟼Tata)} est représentée par 3 nœuds classés suivant les clefs.

Liste simplement chaînée

La raison pour laquelle les listes simplement chaînées sont lentes est que l'on parcourt toute la liste jusqu'au nœud concerné. C'est la même situation qu'une route où l'on passe par tous les villages pour aller d'un endroit à un autre. En ce qui concerne les routes, on a inventé les autoroutes, qui permettent de « sauter » une partie des arrêts : on sort à la sortie précédant le lieu où l'on veut aller et on continue par les petites routes. On va procéder de même avec nos listes. On va introduire une « voie rapide » sur laquelle seule une proportion p de nœuds sera insérée.

On a ainsi deux chaînages : celui par les champs next[0], qui contient tous les nœuds de la liste, et celui par les champs next[1], qui ne contient qu'une proportion p des nœuds (ici p=1/2). Lorsqu'on cherche un élément, on commence par le chaînage de niveau 1 (champs next[1]), on avance tant qu'on rencontre des éléments de clef strictement plus petite que la clef recherchée, puis on passe au chaînage de niveau 0 pour la dernière partie du trajet.

Skip-list de niveau 1

On peut généraliser à des listes de niveau quelconque. Le niveau 0 contient tous les éléments de la liste (au nombre de n). Le niveau k contient (en moyenne) n.pk éléments. À chaque élément est associé un niveau, lequel est tiré au sort lors de l'insertion suivant une distribution adaptée. Un élément de niveau l est inséré dans les chaînages de niveau m pour tout m ≤ l.

Listes d'association

Toutes les fonctions de cette partie devront être placées dans un programme introduit par class AssocList.

Correction : AssocList.java

Attention : en raison de la correction automatique, vous devrez respecter rigoureusement le nom des enregistrements et des fonctions demandées, ainsi que le type de leurs arguments.

On se dotera d'un enregistrement AssocListNode, dont voici la définition :

class AssocListNode {
    AssocListNode next;
    double key;
    String value;

    AssocListNode(double key, String value, AssocListNode next) {
	this.key = key;
	this.value = value;
	this.next = next;
    }

    AssocListNode() {
    }
}

Une liste d'association sera représentée par un nœud initial de type AssocListNode, dont les champs key et value contiendront des valeurs quelconques (par exemple 0.0 et null), suivi de n nœuds contenant les paires d'associations (key, value) successives. Une liste contenant n associations contient donc n+1 objets de type AssocListNode.

On se dotera également d'un enregistrement AssocListPosition, dont voici la définition :

class AssocListPosition {
    AssocListNode position;
    boolean found;

    AssocListPosition(AssocListNode position, boolean found) {
	this.position = position;
	this.found = found;
    }
}

Longueur

Programmez une fonction static int length(AssocListNode origin) qui retourne la longueur de la liste d'association dont le nœud initial est origin. Conformément à ce qui est dit ci-dessus à propos du nœud initial, celui-ci n'est pas pris en compte dans le calcul de la longueur.

Affichage

Programmez une fonction static void print(AssocListNode origin) qui affiche les associations (clef,valeur), dans l'ordre des clefs, sous la forme de lignes de la forme :

clef -> valeur

Ajout d'éléments

Programmez une fonction static AssocListPosition findPos(AssocListNode origin, double key). origin désigne le nœud initial de la liste, lequel ne représente aucune association. Cette fonction doit retourner un objet r de type AssocListPosition tel que :

Programmez une fonction static void put(AssocListNode origin, double key, String value) qui insère l'association keyvalue dans la liste désignée par origin. Si un nœud est déjà présent pour la clef key, on se contente de changer la valeur associée. Indice : appelez la fonction findPos.

Le programme suivant :

    /* OISEAUX 1 */
    public static void main(String[] args) {
	AssocListNode list = new AssocListNode();
	AssocList.put(list, 5., "Pingouin");
	AssocList.put(list, 3., "Manchot");
	AssocList.put(list, 2., "Canard");
	AssocList.put(list, 6., "Bernache du Canada");
	AssocList.put(list, 2.5, "Serin");
	System.out.println(AssocList.length(list));
	AssocList.print(list);
    }

doit produire l'affichage suivant :

5
2.0 -> Canard
2.5 -> Serin
3.0 -> Manchot
5.0 -> Pingouin
6.0 -> Bernache du Canada

Lecture d'éléments

Programmez une fonction static String get(AssocListNode origin, double key) qui retourne la valeur associée à la clef key si elle existe, ou null si la clef key n'existe pas dans la liste. Indice : appelez la fonction findPos.

Nous vous conseillons d'abord de tester votre programme avec l'exemple fourni à la question précédente : faites par exemple afficher la valeur « Pingouin » associée à la clef 5.0.

Vous pourrez ensuite tester votre programme avec notre programme d'essai AssocListTestNoRemove.java. Faites javac AssocListTestNoRemove.java puis java AssocListTestNoRemove 300. Ce programme appelera les fonctions put et get 300 fois, et doit afficher true si tout s'est passé correctement. Sinon, c'est que votre programme est faux.

Suppression d'éléments

Programmez une fonction static AssocListPosition findPreceding(AssocListNode origin, double key). Cette fonction doit retourner un objet r de type AssocListPosition tel que r.position est le dernier élément de clef inférieure strictement à key, ou le nœud d'origine en l'absence d'un tel élément.

Programmez une fonction static void remove(AssocListNode origin, double key) qui doit ôter l'éventuelle association de la clef key.

Le programme suivant :

    /* OISEAUX 2 */
    public static void main(String[] args) {
	AssocListNode list = new AssocListNode();
	AssocList.put(list, 5., "Pingouin");
	AssocList.put(list, 3., "Manchot");
	AssocList.put(list, 2., "Canard");
	AssocList.put(list, 6., "Bernache du Canada");
	AssocList.put(list, 2.5, "Serin");
	AssocList.remove(list, 2.);
	AssocList.remove(list, 3.);
	System.out.println(AssocList.length(list));
	AssocList.print(list);
    }

doit produire l'affichage suivant :

3
2.5 -> Serin
5.0 -> Pingouin
6.0 -> Bernache du Canada

Vous pourrez ensuite tester votre programme avec notre programme d'essai AssocListTestFull.java. Faites javac AssocListTestFull.java puis java AssocListTestFull 300. Ce programme teste les fonctions put, remove et get et doit afficher true, sinon c'est que votre programme est faux.

Constat de non-efficacité

Nos expériences montrent que la performance est en temps quadratique en nombre d'éléments traités, comme on pouvait s'y attendre. Nous allons donc passer aux skip lists, dont le temps moyen est linéaire

Liste simplement chaînée

On constate au passage qu'un fit rapide de courbe donne parfois des résultats un peu amusants, comme la non-monotonie de la complexité...

Skip-lists

Toutes les fonctions de cette partie devront être placées dans un programme introduit par class SkipList, dans le même fichier que le programme précédent.

Correction : SkipList.java

Distribution de probabilité des niveaux

Définissez une constante final static double PROBABILITY=0.5;.

La fonction suivante static int randomLevel(int maxLevel) retourne un entier compris entre 0 et maxLevel inclus, suivant la distribution de probabilité suivante : la probabilité d'obtenir un élément de niveau k, pour tout k <maxLevel, est (1-PROBABILITY)PROBABILITYk, et la probabilité du niveau maxLevel est le complément (1 moins la somme des probabilités des niveaux inférieurs).

Nous rappelons que Math.random() retourne un double pseudo-aléatoire uniformément distribué dans [0,1[.

    static int randomLevel(int maxLevel) {
        int level = 0;
        while(level < maxLevel && Math.random() < PROBABILITY) {
            level++;
        }
        return level;
    }

Type de données

L'enregistrement SkipListNode désignera les nœuds de la skip list. Le champ next est un tableau de l+1 éléments, où l est le niveau du nœud. next[k] pointe sur l'élément suivant de niveau au moins k, ou vaut null en son absence.

Nous choisirons une fois pour toutes un niveau maximal égal à 32 pour tous les éléments de la liste. La liste comprendra un nœud initial de niveau maximal, dont on ignorera les champs key et value (il ne représente pas un élément). Une liste représentant n associations clefvaleur aura donc n+1 nœuds.

class SkipListNode {
    SkipListNode[] next;
    double key;
    String value;

    SkipListNode() {
        next = new SkipListNode[32];
    }
}

Vous pourrez avoir besoin d'autres constructeurs, que vous programmerez à votre guise.

On se dotera également d'un enregistrement SkipListPosition permettant de désigner des positions dans la liste.

class SkipListPosition {
    SkipListNode[] positionAtLevel;
    int foundLevel;
}

Longueur

Programmez une fonction static int length(SkipListNode origin) qui retourne la longueur de la liste d'association dont le nœud initial est origin. Conformément à ce qui est dit ci-dessus, le nœud initial ne compte pas dans le calcul de la longueur.

Affichage

Programmez une fonction static void print(SkipListNode origin) qui affiche les associations (clef,valeur), dans l'ordre des clefs, sous la forme de lignes de la forme :

clef -> valeur

Ajout d'éléments

Programmez une fonction static SkipListPosition findPos(SkipListNode origin, double key). origin désigne le nœud initial de la liste, lequel ne représente aucune association. Cette fonction doit retourner un objet r de type SkipListPosition tel que :

Un exemple est détaillé ci-dessous.

Programmez une fonction static void put(SkipListNode origin, double key, String value) qui insère l'association (key, value) dans la liste désignée par origin. Si un nœud est déjà présent pour la clef key, on modifie son champ value. Sinon, le niveau du nouveau noeud est tiré aléatoirement par la fonction randomLevel. Indice : appelez la fonction findPos.

Exemple : vous désirez insérer l'association 2⟼Xilinx dans la skip-list figurée ci-dessous en noir, qui contient les associations 0⟼Toto, 1⟼Tata, 3⟼lapin, 7⟼Tata. On a choisi le niveau maximal m=3. Vous commencez par appeler findPos, qui vous retourne un objet r de type SkipListNode tel que r.foundLevel vaut -1 (normal, pas de clef 2) et r.positionAtLevel est figuré en rouge. Votre générateur aléatoire a décidé que l'association 2⟼Xilinx doit être représentée par un nœud de niveau 3, représenté en bleu.

Skip-list de niveau 3

Testez votre programme avec l'exemple OISEAUX 1 ci-dessus en remplaçant bien sûr tout ce qui parle de AssocList par des SkipList.

Lecture d'éléments

Programmez une fonction static String get(SkipListNode origin, double key) qui retourne la valeur associée à la clef key si elle existe, ou null si la clef key n'existe pas dans la liste. Indice : appelez la fonction findPos.

Vous pourrez tester votre programme avec notre programme d'essai SkipListTestNoRemove.java. Faites javac SkipListTestNoRemove.java puis java SkipListTestNoRemove 300. Ce programme teste les fonctions put et get et doit afficher true, sinon c'est que votre programme est faux.

Si vous voulez vous assurer que votre programme a bien une complexité (quasi) linéaire, essayez java SkipListTestNoRemove 100000. Normalement, cela doit prendre au plus quelques secondes. Si votre programme met plus longtemps, c'est que sa complexité est incorrecte.

Suppression d'éléments

Programmez une fonction static SkipListPosition findPreceding(SkipListNode origin, double key). Cette fonction doit retourner un objet r de type SkipListPosition tel que pour tout niveau 0 ≤ korigin.next.length-1, r.positionAtLevel[k] est le dernier élément de niveau au moins k de clef inférieure strictement à key, ou le nœud d'origine en l'absence d'un tel élément.

Programmez une fonction static void remove(SkipListNode origin, double key) qui doit ôter l'éventuelle association de la clef key.

Testez votre programme avec l'exemple OISEAUX 2 ci-dessus en remplaçant bien sûr tout ce qui parle de AssocList par des SkipList.

Vous pourrez ensuite tester votre programme avec notre programme d'essai SkipListTestFull.java. Faites javac SkipListTestFull.java puis java SkipListTestFull 300. Ce programme teste les fonctions put, remove et get et doit afficher true, sinon c'est que votre programme est faux.

Constat de complexité linéaire

Si vous voulez vous assurer que votre programme est bien en complexité n log n, essayez java SkipListTestFull 100000. Normalement, cela doit prendre au plus quelques secondes. Si votre programme met plus longtemps, c'est que sa complexité est incorrecte.

Normalement, on constate bien une complexité linéaire :

Skip-list

Bibliographie

Attention : ces liens pointent vers des serveurs externes et ne sont donc pas accessibles pendant l'examen sur machines.