Structures de
données

Algorithmes

Transparents repris d'un cours donné par Jean-Charles Régin à l'Université de Nice.

• Chemin dans un graphe : votre GPS, votre téléphone IP, tout ce qui est acheminement (la Poste)
• Flots : affectations, emploi du temps, bagages (aéroport), portes d'embarquement
• Scheduling (ordonnancement) fabrication de matériel dans les usines, construction automobile
• Compression/Décompression : MP3, xvid, divx, h264 codecs audio et vidéo tar zip vidéo, tar, zip.
• Cryptage : RSA (achat électronique)
• Internet : Routage des informations, moteurs de recherche
• Simulation : Prévision météo, Explosion nucléaire
• Traitement d’images (médecine), effets spéciaux (cinéma)

Exemples :

[chemin] Pour résoudre un labyrinthe, toujours longer le mur de droite.

[tri] Chercher les minimas successifs (sans remise) dans un ensemble fini d'entiers revient à les trier

[cryptage] Remplacer chaque lettre d'un message par la suivante dans l'alphabet

...

Remonte à l'Antiquité
    Euclide : calcul du pgcd de deux nombres,
    Archimède : calcul d’une approximation de £\pi£

S'étudient à l'aide des mathématiques : on peut par exemple montrer que l'algorithme de tri du slide précédent est correct par récurrence

...Mais se trouvent pleinement exploités en informatique :

• Hardware (algorithmes d'addition, multiplication... dans le processeur)
• Software (logiciels de retouche photo, de montage audio/vidéo, ...)

Classes d'algorithmes

On peut ranger les algorithmes dans diverses catégories en fonction (de l'équivalent mathématique) du

• temps d'exécution en fonction de la taille £n£ de l'entrée
• nombre d'opérations "élémentaires" nécessaires en fonction de £n£

£\Rightarrow£ Théorie de la complexité

En pratique, on retient en général qu'un algorithme doit avoir un temps d'exécution et un nombre d'opérations au maximum en £n^3£ pour être utile.

Exemple : le produit matriciel usuel est en £O(n^3)£

Algorithme : preuve

• On peut prouver les algorithmes !
• Un algorithme est dit totalement correct si pour tout jeu de données il termine et rend le résultat attendu
• C'est assez difficile, mais c’est important.
  • Codage/Décodage des données £\rightarrow£ si bug, tout est perdu
  • Centrale nucléaire
  • Aérospatiale
  • Métro automatique

Attention : un algorithme juste peut être mal implémenté

Algorithme : résumé

• C'est ancien
• C'est fondamental en informatique
• Ça se prouve
• On estime le temps de réponse et la mémoire utilisée

Exercices

Structures de données

Pour passer de l'énoncé d'un algorithme à son implémentation dans un ordinateur, il est nécessaire de préciser comment seront stockées et manipulées les données impliquées

Ces choix sont cruciaux : l'efficacité d'un algorithme dépend en grande partie des structures de données utilisées pour l'implémenter

Précision...

• sa définition abstraite à partir des opérations qu'elle effectue sur les données
• son implémentation concrète dans la mémoire de l'ordinateur (en général il y a le choix !)

Exemple :

Tableaux

Notation : £T[i]£ désigne l'élément d'indice £i£ du tableau £T£

• Accès et modification d'un élément en temps constant : £O(1)£
• Insertion / suppression d'un élément "impossible" (coût £O(n)£)

[concret] Les éléments d'un tableau sont contigus en mémoire.

Tableaux redimensionnables

Ajout (ou suppression) d'un élément en £O(1)£ en fin de tableau

Soit £T£ un tableau standard. On lui associe un entier £C£ désignant sa capacité maximale. Initialement on peut prendre £C£ = taille du tableau (notée £\ell£).

Contrepartie : le tableau n'a pas d'adresse mémoire fixe

Tableau dynamique : complexité

Soient £\ell_i£ et £C_i£ les taille et capacité initiales du tableau.

L'ajout de £m£ éléments nécessite £R = \left \lceil \log_2 \frac{\ell_i - C_i + m}{C_i} \right \rceil£ réallocations + recopies.

Comptons les opérations élémentaires (copie d'un élément) :

£\sum_{j=0}^{R-1} (C_i 2^j + 1)£ £\simeq C_i 2^R£
£\sum_{j=0}^{R-1} (2^j C_i + 1)£ £\simeq \ell_i - C_i + m£
£\sum_{j=0}^{R-1} (2^j C_i + 1)£ £= O(m)£

En moyenne, l'ajout d'un élément se fait donc en £O(1)£ [complexité amortie]

Piles, files

Piles

Une pile (stack en anglais) est une structure de données fondée sur le principe "dernier arrivé, premier sorti" (ou LIFO pour Last In, First Out)

£\Rightarrow£ les derniers éléments ajoutés à la pile seront les premiers à être récupérés.

Une des structures de données les plus fondamentales en informatique : très simple et puissante.

Pile : opérations

Sommet(P) :
   renvoie le dernier élément ajouté et non encore retiré (top)

Empiler(P,elt) :
   place l'élément au sommet de la pile P (push)

Dépiler(P) :
   retire de la pile le sommet (pop)

EstVide(P) :
   Renvoie vrai si la pile est vide et faux sinon (empty)

Exemple — vérification de parenthésage

Algorithme : on empile les parenthèses ouvrantes, et à chaque parenthèse fermante rencontrée on dépile un élément.

32+a*((4-6/(b+3)*51)-1)

Files

"Inverse" d'une pile : c'est l'analogue d'une file d'attente £\Rightarrow£ first-in-first-out

Exemples :

• Serveur d'impression traite les requêtes dans l'ordre d'arrivée
• Algorithme de parcours en largeur d’un graphe

Question : Sdd pour le parcours d'un graphe en profondeur ?

Question : ...Une pile

Listes

L'accès aux éléments d'une liste se fait de manière séquentielle : chaque maillon permet l'accès au suivant.

La recherche d'un élément donné est donc coûteuse (comparée au cas du tableau). Cependant, l'insertion et la suppression peuvent s'effectuer en temps constant

Illustration

Un maillon de la châine contient une donnée et un accès vers un autre maillon (éventuellement vide)

• Premier(L) = e1 (head)
• Suivant(e1) = e2 (next)
• Suivant(e2) = e3
• Suivant(e3) = NULL

Variantes

Liste circulaire

Le "dernier" élément a pour suivant le "premier"

Liste doublement chaînée

Chaque maillon pointe à la fois sur le suivant et le précédent

Exercice

Décrire les opérations à effectuer pour insérer elt après p

Arbres

Structure hiérarchique définie récursivement :

• L'ensemble vide est un arbre, tout singleton est un arbre
• Soient £S£ un singleton et £A_1,\dots,A_n£ des arbres.
  Alors £(S,A_1,\dots,A_n)£ est également un arbre

£\Rightarrow£ un arbre est composé d'un sommet et de sous-arbres.

• Le sommet est appelé racine ;
• un sous-arbre réduit à un singleton est une feuille

Illustration

Définitions

Analogie généalogique...

• k^eme enfant d'un noeud N = sommet du k^eme sous-arbre de N
• Parent de N = noeud dont N est l'enfant

Également frères/soeurs, ancêtres, descendants, cousin(e)s...

• Profondeur d'un noeud = longueur du chemin vers la racine
• Hauteur d'un arbre = profondeur maximale d'un noeud

Schématisation

Arbre binaire : cas particulier où chaque noeud a au plus deux fils ;
Arbre binaire : adapté pour la recherche par comparaisons

• plus grande que toutes celles du sous-arbre gauche,
• plus petite que toutes celles du sous-arbre droit

Intérêt : peu de comparaisons si faible hauteur

Application

Rechercher 12 depuis la racine

Généralisation

Chaque clé est associée à une adresse mémoire : celle de la donnée recherchée

B-tree

Arbre ordonné avec des contraintes particulières (pour que la recherche soit toujours efficace)

£\Rightarrow£ Structure couramment utilisé dans les bases de données
£\Rightarrow£ pour indexer les données ; i.e., y accéder rapidement.

Illustrations

Propriétés

Remarque : l'insertion et la suppression ne sont pas triviales

Plus d'informations

Variantes

[Wikipedia]

• B+tree : copies of the keys are stored in the internal nodes; the keys and records are stored in leaves; in addition, a leaf node may include a pointer to the next leaf node to speed sequential access (Comer 1979).
• B*tree : balances more neighboring internal nodes to keep the internal nodes more densely packed (Comer 1979). This variant requires non-root nodes to be at least 2/3 full instead of 1/2 (Knuth 1998).
• Order statistic trees : supports two additional operations beyond insertion, lookup and deletion:
  • Select(i) — find the i^th smallest element stored in the tree
  • Rank(x) — find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

Bilan

[Wikipedia] a B-tree:

• keeps keys in sorted order for sequential traversing
• uses a hierarchical index to minimize the number of disk reads
• uses partially full blocks to speed insertions and deletions
• keeps the index balanced with an elegant recursive algorithm

In addition, a B-tree minimizes waste by making sure the interior nodes are at least half full. A B-tree can handle an arbitrary number of insertions and deletions.

Index

+ Efficacité nettement augmentée si index bien choisi

 - Il faut mettre à jour les index à chaque insertion/suppression

Différents types d'index possible. Le plus courant étant le B-tree (ou variantes)

Description d'un index SQL

• An index is a distinct structure in the database that is built using the create index statement.
• It requires its own disk space and holds a copy of the indexed table data.

Analogie : index en fin d'ouvrage scientifique

Feuilles du B-tree

Databases use doubly linked lists to connect the so-called index leaf nodes.

£\Rightarrow£ The index order is maintained on two different levels: the index entries within each leaf node, and the leaf nodes among each other using a doubly linked list

B-tree : Balanced search tree

Balanced : toutes les feuilles ont la même profondeur

• The doubly linked list establishes the logical order between the leaf nodes.
• The root and branch nodes support quick searching among the leaf nodes.

Each branch node entry corresponds to the biggest value in the respective leaf node.

B-tree traversal

Index fragment to illustrate a search for the key "57". The tree traversal starts at the root node on the left-hand side. Each entry is processed in ascending order until a value is greater than or equal to the search term (57)

The tree traversal is a very efficient operation, because of:

• tree balancing
• logarithmic grow

Index lent ?

Le parcours de l'arbre pour atteindre une feuille a une longueur bornée, donc n'impacte pas la performance

En revanche, il peut y avoir beaucoup d'entrées possédant la même clé, forçant l'algorithme de recherche à parcourir plusieurs entrées d'une même feuille, voire plusieurs feuilles (liste chaînée). Il faut ensuite récupérer les entrées dans la table. Tout cela prend du temps.

£\Rightarrow£ Il faut faire attention à la façon dont on écrit les requêtes.

Index dans PostgreSQL

£\rightarrow£ Automatiquement créés sur les clés primaires

Sinon...

CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name ] ON table [ USING method ]
    ( { column | ( expression ) } [ COLLATE collation ] [ opclass ] 
        [ ASC | DESC ] [ NULLS { FIRST | LAST } ] [, ...] )
    [ WITH ( storage_parameter = value [, ... ] ) ]
    [ TABLESPACE tablespace ]
    [ WHERE predicate ]

Index automatiques

Les champs marqués "UNIQUE" sont également indexés :

-- dans psql sur 192.168.31.236 : 
create table test (
   id serial primary key, 
   name varchar(30) unique, 
   date timestamp);

NOTICE:  CREATE TABLE créera des séquences implicites 
   « test_id_seq » pour la colonne serial « test.id »
NOTICE:  CREATE TABLE / PRIMARY KEY créera un index 
   implicite « test_pkey » pour la table « test »
NOTICE:  CREATE TABLE / UNIQUE créera un index implicite 
   « test_name_key » pour la table « test »

Optimisation de requêtes

La clause WHERE

The where clause defines the search condition of an SQL statement, and it thus falls into the core functional domain of an index: finding data quickly.

Although the where clause has a huge impact on performance, it is often phrased carelessly so that the database has to scan a large part of the index.

The result: a poorly written where clause is the first ingredient of a slow query.

£\Rightarrow£ On se focalise dans ce cours sur le WHERE seulement

EXPLAIN [ANALYZE] ...

Given a query:

SELECT last_name FROM employees where salary >= 50000;

We can inspect how Postgres will execute it with:

EXPLAIN SELECT last_name FROM employees where salary >= 50000;
                         QUERY PLAN
--------------------------------------------------------------
Seq Scan on employees  (cost=0.00..16.50 rows=173 width=118)
  Filter: (salary >= 50000)

We can both execute the query and inspect the path/time it took with:

EXPLAIN ANALYZE SELECT last_name FROM employees 
    where salary >= 50000;
                         QUERY PLAN
--------------------------------------------------------------
Seq Scan on employees  (cost=0.00..16.50 rows=173 width=118)
    (actual time=0.018..0.018 rows=0 loops=1)
  Filter: (salary >= 50000)
Total runtime: 0.053 ms

Opérateur égal

Index sur clé primaire

We start with the simplest yet most common where clause: the primary key lookup. We use the EMPLOYEES table defined as follows:

CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   date_of_birth DATE           NOT NULL,
   phone_number  VARCHAR2(1000) NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
);

SELECT first_name, last_name 
   FROM employees 
   WHERE employee_id = 123

          QUERY PLAN
---------------------------------
Index Scan using employees_pk
(cost=0.00..8.27 rows=1 width=14)
Index Cond: 
  (employee_id = 123::numeric)

Concatenated indexes

Supposons que l'entreprise fusionne avec une autre : employee_id n'est alors plus unique. On ajoute un champ 'subsidiary_id' désignant l'entreprise.

£\Rightarrow£ La clé primaire devient (employee_id, subsidiary_id)

Un index est alors construit de la même façon que sur une colonne unique, mais l'ordre importe

Exemple de l'annuaire téléphonique : clé = (nom, prénom)
£\rightarrow£ On cherche d'abord le nom, puis le prénom !

Visualisation

SELECT first_name, last_name, date_of_birth
  FROM employees
  WHERE date_of_birth >= TO_DATE('1971-01-01', 'YYYY-MM-DD')
    AND date_of_birth <= TO_DATE('1971-01-09', 'YYYY-MM-DD')
    AND subsidiary_id  = 27

Fonctions

On ne peut pas utiliser de fonctions d'un index en conservant ses propriétés :

SELECT *
  FROM employees
  WHERE UPPER(last_name) 
    = 'WINAND'

         QUERY PLAN
------------------------------
Seq Scan on employees [...]
  Filter:
  (upper((last_name)::text) = 
     'WINAND'::text)

CREATE INDEX emp_up_name 
   ON employees (UPPER(last_name));

User-defined functions

On peut utiliser des fonctions PL/pgSQL quelconques pour définir un index (exemple : date_de_décès - date_de_naissance), mais elles doivent être déterministes.

Contre-exemple :

CREATE FUNCTION get_age(date_of_birth DATE) 
RETURNS integer AS $$
BEGIN 
  RETURN TRUNC(MONTHS_BETWEEN(SYSDATE, date_of_birth)/12);
END $$ language plpgsql;

get_age(X) change à chaque anniversaire de X...

Index partiel

Les emails circulant sur le web sont en grande majorité du spam (~90%).

• publicité,
• demande d'argent,
• ...,

CREATE INDEX messages_spam
   ON messages (receiver)
   WHERE spam_flag = ...

Exemple

CREATE TABLE messages (
  sender VARCHAR(64) NOT NULL,
  receiver VARCHAR(64) NOT NULL,
  subject VARCHAR(256),
  content TEXT,
  spam_flag BOOLEAN
);

Avec l'index précédent :

SELECT *
  FROM messages
  WHERE subject LIKE 'Hello%' AND spam_flag = TRUE

Données ordonnées

Par défaut les données n'ont pas d'ordre dans une table (elles sont stockées au fur et à mesure des insertions).

..."sauf" dans les indexes, où leurs adresses sont rangées "à leur place"

CLUSTER [VERBOSE] table_name [ USING index_name ]

Bonus : quiz

Extrait : CREATE INDEX tab_idx ON tbl (a, date_column);

SELECT date_column, count(*)
  FROM tbl
  WHERE a = 123
  GROUP BY date_column;

SELECT date_column, count(*)
  FROM tbl
  WHERE a = 123
    AND b = 42
  GROUP BY date_column;

Explications.