Planche 1
PC6
Jean-Jacques.Levy@inria.fr
http://www.polytechnique.fr/poly/~levy/
INRIA -- Rocquencourt
tel: 01 39 63 56 89


secrétariat: Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX
tel: 34 67

http://w3.edu.polytechnique.fr/informatique/

Planche 2
Plan

  1. Exceptions
  2. Types paramétrés --- Polymorphisme
  3. Listes associatives
  4. Recherche en table
  5. Hachage
  6. Listes de collision
  7. Adressage ouvert
  8. Hachage multiple
Planche 3
Exceptions

Une fonction peut abandonner son exécution à cause d'un argument incorrect ou d'une erreur dans son exécution. Trois solutions:

Avantage des exceptions: ne pas réserver de valeur pour le cas anormal, séparer les traitements des cas normaux ou erreurs.

Planche 4
Exceptions 

static int head (List x) throws Exception {
  if (x == null)
    throw new Exception ("Pile Vide");
  else
    return x.hd;
}
On peut être plus précis et définir ses propres exceptions

static int head (List x) throws EmptyStackException {
  if (x == null)
     throw new EmptyStackException();
  else
    return x.hd;
}

class EmptyStackException extends Exception { }
Planche 5
Exceptions en Ocaml -- bis 

try {
. . .
} catch (EmptyStackException e) {
    // traitement savant
}
catch (Exception e) {
    System.err.println("Exception caught: " + e.getMessage());
}
finally {
    // traitement fait qu'on passe ou non par une exception
    // utile pour fermer un fichier, etc.
}
Planche 6
Exceptions en Ocaml 

exception Empty_list;;
exception Empty_list

let head l =
    match l with
      [] -> raise Empty_list
    | hd :: tl -> hd;;

head [];;
Uncaught exception: Empty_list
Un certain nombre d'exceptions pré-existent Exit, Not_found, Failure, Division_by_zero, Sys_error, ...

Planche 7
Exceptions en Ocaml -- bis

L'instruction try permet d'attraper une exception (avec filtrage)

try 
...
with (Failure s) ->
   printf "Failure %s\n" s
Planche 8
Surcharge en Java

Une même fonction peut avoir deux sens différents selon le type de ses arguments.

Par exemple, Sys.out.println dans la classe java.io.PrintStream

public void println()
public void println(boolean x)
public void println(int x)
public void println(double x)
public void println(String x)
Cela peut servir pour les constructeurs. On peut en avoir sans arguments ou avec plusieurs sortes d'argument. + est le seul opérateur surchargé (contrairement à C++).

Attention à ne pas trop utiliser la surcharge, car rapidement incompréhensible (surtout si mélangé au mécanisme des sous-classes).

La surcharge est résolue à la compilation (donc avant l'exécution).

Planche 9
Types polymorphes

Plusieurs des types prédéfinis de Ocaml --- tableaux, listes mais aussi tuples et fonctions --- sont paramétrés: pour les utiliser il faut préciser avec quels types leurs valeurs sont construites. On peut aussi déclarer ses propres types paramétrés ou polymorphes.

type 'a monome = {degré: int; coeff: 'a} ;;
type complexe = {re: float; im: float} ;;
Alors: 
let x = [{degré = 3; coeff = 1.2}] ;;
val x : float monome list = [exp=3; coeff=1.2]
let x = [{degré = 3; coeff = {re=2.3; im=3.0} }] ;;
val x : complexe monome list = [degré=3; coeff=re=2.3; im=3]
Il n'y a pas de type paramétré général ``enregistrement''.
Planche 10
Listes associatives

Listes dont les éléments servent à ranger une valeur sous une clé permettant de les retrouver. 
type ('a, 'b) elem = {cle: 'a; valeur: 'b};;
let rec afind k = function
  e :: al -> if e.cle = k then e.valeur else afind k al
| []      -> raise Not_found;;
On peut utiliser des a-listes modifiables pour gérer un répertoire : 
type entree = {nom: string;
               mutable adresse: string list}
and  repertoire = {mutable entrees: entree list};;
let modif n a r =
   let rec loop = function
     e :: al ->
       if e.nom = n then e.adresse <- a else loop al
   | [] ->
       r.entrees <- {nom=n; adresse=a}::r.entrees
   in loop r.entrees;;
Planche 11
Recherche en table

Si le nombre d'entrées est prévisible, on peut ranger les éléments dans un tableau au lieu d'une liste : 
type ('a, 'b) table = {mutable nb:int; tab: ('a, 'b) elem array};;
let ajout k v t =
  let j = ref 0 in
  while !j < t.nb && t.tab.(!j).cle <> k do
    incr j;
  done;
  if !j = t.nb then t.nb <- !j+1;
  t.tab.(!j) <- {cle=k; valeur=v};;
Planche 12
Recherche en table par dichotomie

Si les éléments sont rangés par clé croissante, on peut faire une recherche dichotomique, en O(log n) au lieu de O(n).

let dicho k t =
  let rec cherche g d =
    if d <= g then raise Not_found
    else let m = (g+d) / 2 in
         let km = t.tab.(m).cle in
         if km = k then t.tab.(m).valeur
         else if km > k then cherche g m
         else cherche (m+1) d
  in cherche 0 t.nb;;
Si on connaît la répartition, on peut même faire une recherche par interpolation, en O(log log n).
Planche 13
Hachage

Planche 14
Hachage et collisions

Si h(i)=h(j) ``par hasard'', que faire?
Plusieurs solutions :
Planche 15
Listes de collision

On hache dans un tableau de a-listes 
type eltabhash = {m: int; eltab: entree list array};;
let mkltab m = {m = m; eltab = Array.make m []};;
let lookup n {m = m; eltab = t} =
   let i = hache m 128 n in
   let rec loop = function
      e :: l -> if e.nom = n then e.adresse else loop l
   |  [] -> raise Not_found
   in loop t.(i);;
let insert n a {m=m; eltab=t} =
   let i = hache m 128 n in
   let rec loop = function
      e :: l ->
        if e.nom = n then e.adresse <- a else loop l
   |  [] ->
        t.(i) <- {nom=n; adresse=a}::t.(i)
   in loop t.(i);;
Complexité en O(n/m).
Planche 16
Adressage ouvert

On range directement les entrées dans le tableau, et en cas de collision on fait une bête recherche linéaire. Il faut pouvoir borner le nombre maximum d'entrées. On utilise une valeur spéciale pour repérer les cases libres. 
type ('a, 'b) otabhash = {m:int; etab: ('a, 'b) elem array};;
let elemVide = {cle = -1; valeur = []};;
let estVide t i = t.(i) == elemVide;;
let mkotab m = {m = m; etab = Array.make m elemVide};;
let insert k v {m = m; etab = t} =
   let i = ref (k mod m) in
   while not (estVide t !i) && t.(!i).cle <> k do
     i := (!i+1) mod m
   done;
   t.(!i) <- {cle = k; valeur = v};;
Planche 17
Adressage ouvert -- bis

La complexité ne dépend que du taux d'occupation a=n/m, et vaut :
1/ 2(1+1/ 1-a2) 10cmpour une insertion
(recherche avec échec),
1/ 2(1+1/ 1-a) pour une recherche avec succès.

Pour a=66%, on fait 5 et 2.
Pour a=90%, on fait 50 et 5.

Pour accélerer on peut faire un double hachage, en augmentant i par pas de u=h2(k), où h2 est une seconde fonction de hachage, au lieu de pas de 1.
On fait alors 1/ 1 - a et 1/ a ln (1/ 1-a), soit
pour a = 80%, 5 et 1,3;
pour a = 99%, 100 et 5.
Planche 18
Hachage multiple

Planche 19
Exercices en TD

This document was translated from LATEX by HEVEA.