Données, structures de données et algorithmes, et pourquoi la vitesse en dépend

Tout n’est que bits

Les ordinateurs stockent tout sous forme de bits : des chiffres binaires qui valent soit 0, soit 1. Physiquement, un bit peut être une minuscule charge électrique, une zone magnétique sur un disque ou une impulsion lumineuse dans une fibre, mais pour le logiciel ce n’est qu’une valeur parmi deux. Huit bits forment un octet, qui peut contenir 2⁸ = 256 motifs différents, de 00000000 à 11111111.

Les tailles se construisent à partir de là. Un kilooctet vaut environ mille octets, un mégaoctet environ un million, un gigaoctet environ un milliard et un téraoctet environ mille milliards. (En toute rigueur, les préfixes standard kilo, méga et giga désignent des puissances de 1000 ; la mémoire se mesure souvent en puissances de 1024, pour lesquelles existent les unités kibioctet, mébioctet et gibioctet. La différence compte rarement pour la conception, mais elle explique pourquoi un disque de « 1 To » affiche moins dans certains gestionnaires de fichiers.) Une page de texte brut fait quelques kilooctets, une photo prise au téléphone quelques mégaoctets, une heure de vidéo haute définition quelques gigaoctets.

Les bits ne signifient rien à eux seuls. Le motif 01000001 peut être le nombre 65, la lettre A, une partie d’une couleur dans une photo ou une partie d’une instruction pour le CPU. Ce qui donne un sens aux bits, c’est la convention sur la façon de les lire : c’est l’idée de type de données.

Les types de données : nombres, texte, vrai ou faux

Un type de données indique à un programme quel genre de valeur est une donnée, et donc quelles opérations ont un sens. Tout langage de programmation possède quelques types de base, et ceux de Python sont représentatifs.

Les entiers sont des nombres sans partie décimale, comme 3, 0 ou -42, qui servent à compter : les articles d’un panier, les sièges d’un vol. Les nombres à virgule flottante (flottants), comme 12,5 ou 0,2, représentent les nombres décimaux de façon approchée, en binaire. Comme beaucoup de nombres décimaux n’ont pas de forme binaire exacte, 0.1 + 0.2 donne 0.30000000000000004 en Python. Cela convient à la physique et aux graphismes, mais pas à l’argent : c’est pourquoi les systèmes financiers stockent les montants en nombres entiers de pence ou de centimes, ou utilisent un type décimal (Python dispose de decimal.Decimal). Les booléens n’ont que deux valeurs, True et False, et enregistrent des faits de type oui ou non, comme « cette commande a-t-elle été payée ? ». Les chaînes sont du texte, comme le nom d’un client. Les systèmes réels ajoutent d’autres types par-dessus : dates et heures, montants monétaires et données binaires comme les images.

Les types comptent au-delà d’un seul programme. Quand deux systèmes échangent des données, ils doivent s’accorder sur les types autant que sur les valeurs : un code postal est-il un nombre ou du texte (du texte : certains commencent par des lettres, et certains codes numériques commencent par zéro) ? Une date est-elle au format jour-mois ou mois-jour, et dans quel fuseau horaire ? Beaucoup de bugs d’intégration coûteux sont des désaccords sur les types.

Le texte et UTF-8

Le texte est stocké en attribuant un numéro à chaque caractère, puis en stockant ces numéros sous forme d’octets. La norme internationale Unicode attribue un numéro, appelé point de code, à bien plus de cent mille caractères issus des écritures du monde entier, plus des symboles et des emoji. Un encodage décide ensuite comment ces numéros deviennent des octets. Aujourd’hui, l’encodage dominant, sur le web et dans la plupart des nouveaux systèmes, est UTF-8.

UTF-8 utilise un nombre variable d’octets par caractère : un octet pour les lettres de base de l’anglais, les chiffres et la ponctuation (si bien qu’un texte qui n’utilise que ces caractères est identique, octet pour octet, en UTF-8 et dans l’encodage ASCII, bien plus ancien), deux octets pour des caractères comme é, trois pour des caractères comme € et la plupart des caractères chinois, japonais et coréens, et quatre pour les emoji et certaines écritures plus rares. Cela a une conséquence pratique : le nombre de caractères d’une chaîne et le nombre d’octets qu’elle occupe peuvent différer. Une colonne de base de données limitée à 50 octets ne pourra peut-être pas contenir un nom de 50 caractères écrit en grec.

Le bug de texte classique, ce sont les caractères illisibles (par exemple Café au lieu de Café), qui apparaissent quand des octets écrits dans un encodage sont lus dans un autre. Le remède est simple à énoncer : utiliser UTF-8 partout, et le dire explicitement chaque fois que du texte franchit une frontière, comme un fichier, une base de données ou un message réseau.

Les structures de données : des façons d’organiser les données

Les programmes traitent rarement une seule valeur à la fois. Une structure de données est une façon d’organiser de nombreuses valeurs en mémoire pour que les opérations dont vous avez besoin soient rapides. Le bon choix peut faire la différence entre une page qui se charge instantanément et une page qui ne se charge jamais. Chacune a son analogie dans la vie quotidienne.

Une liste (appelée tableau dans beaucoup de langages) garde les éléments dans l’ordre, comme une liste de courses numérotée. Obtenir le cinquième élément est instantané, car l’ordinateur peut calculer où il se trouve. Trouver un élément d’après sa valeur oblige à vérifier les éléments un par un. Un dictionnaire (appelé aussi map ou table de hachage) range des valeurs sous des clés uniques, comme un vestiaire : vous tendez le ticket C377 et vous récupérez aussitôt le bon manteau, sans regarder tous les manteaux. Un ensemble est une collection sans doublons, comme une liste d’invités, et répond rapidement à la question « cette personne y figure-t-elle ? ».

Une file fonctionne comme une file d’attente au guichet de la poste : premier entré, premier sorti. Les systèmes utilisent des files pour le travail en attente, comme les commandes qui attendent la cuisine. Une pile fonctionne comme une pile d’assiettes : dernier entré, premier sorti. Le bouton Précédent de votre navigateur en utilise une : la page que vous avez visitée le plus récemment est la première à laquelle vous revenez. Un arbre a une seule racine avec des branches en dessous, comme un arbre généalogique ou les dossiers de votre ordinateur ; c’est aussi grâce aux arbres que les bases de données gardent les données triées pour des recherches rapides. Un graphe est un ensemble d’éléments (nœuds) reliés par des liens (arêtes) selon n’importe quel schéma, comme une carte routière ou un réseau social, et répond à des questions comme « quel est le plus court chemin ? » ou « qui sont les amis de mes amis ? ».

basket = ["pizza", "cola", "pizza"]            # list: ordered, duplicates allowed
print(basket[0])                                # by position: "pizza"

customers = {"C102": "Ana", "C377": "Chen"}      # dictionary: key to value
print(customers["C377"])                        # by key: "Chen"

voted = {"ana@example.com", "ben@example.com"}   # set: no duplicates
print("ana@example.com" in voted)              # True

from collections import deque
kitchen = deque(["order 1", "order 2"])         # queue
kitchen.append("order 3")                       # joins at the back
print(kitchen.popleft())                        # served first: "order 1"

Les algorithmes

Un algorithme est une méthode précise, étape par étape, pour résoudre un problème, et qui se termine toujours : comme une recette, mais sans aucune place pour l’interprétation. Trier une liste de noms, trouver le plus court chemin entre deux adresses, vérifier si un mot de passe correspond et décider quelle publicité afficher, tout cela est fait par des algorithmes.

Il existe généralement plus d’un algorithme pour un même problème, et la quantité de travail qu’ils font peut varier énormément. Imaginez que vous cherchiez un nom dans un annuaire téléphonique imprimé. Vous pourriez commencer à la première page et lire chaque entrée jusqu’à le trouver : c’est correct, mais lent. Ou vous pourriez ouvrir l’annuaire au milieu, regarder si le nom vient avant ou après cette page, écarter la moitié qui ne peut pas le contenir, et recommencer. Comme l’annuaire est trié, chaque coup d’œil divise par deux les pages restantes. Cette seconde méthode s’appelle la recherche dichotomique, et pour un annuaire d’un million de noms, elle demande environ 20 coups d’œil au lieu de jusqu’à un million.

Grand O : comment le travail augmente avec les données

Les ingénieurs décrivent comment le coût d’un algorithme augmente à l’aide de la notation grand O. Elle ignore le temps exact sur une machine particulière et pose une seule question : si la quantité de données, appelée n, devient dix ou mille fois plus grande, combien de travail en plus faut-il ? Elle décrit le pire cas, sauf mention contraire, et elle ignore les facteurs constants, ce qui fait à la fois sa force (elle saisit la forme de la croissance) et sa faiblesse (deux algorithmes en O(n) peuvent quand même différer d’un facteur dix en pratique).

O(1), temps constant : le travail ne dépend pas de n. Chercher une clé dans un dictionnaire est en O(1) en moyenne. O(log n), logarithmique : le travail augmente d’une étape chaque fois que n double, comme la recherche dichotomique. O(n), linéaire : deux fois plus de données, deux fois plus de travail, comme le parcours d’une liste. O(n log n) : un peu moins bien que linéaire ; les bons algorithmes de tri généralistes fonctionnent à ce rythme. O(n²), quadratique : deux fois plus de données, quatre fois plus de travail. Cela apparaît typiquement quand, pour chaque élément, un programme parcourt tous les autres éléments, par exemple pour comparer chaque client à tous les autres afin de trouver les doublons.

Lisez attentivement la dernière colonne. À un milliard d’étapes simples par seconde, un algorithme en million au carré a besoin de mille milliards d’étapes : environ un quart d’heure de calcul pur, et en pratique bien plus. Le même travail fait avec une méthode en O(n log n) prend une petite fraction de seconde. Un code qui semblait correct pendant les tests avec 1000 clients peut s’enliser complètement avec un million, et aucune quantité de matériel supplémentaire ne sauvera longtemps un algorithme quadratique.

L’espace contre le temps

Le dictionnaire de l’exemple commenté est plus rapide parce qu’il utilise de la mémoire supplémentaire pour organiser les données à l’avance. C’est l’un des compromis les plus courants en informatique : on peut souvent acheter de la vitesse avec de l’espace, ou économiser de l’espace en dépensant du temps.

Un index est un ensemble de données supplémentaires, conservé à côté des données principales, qui répond rapidement à un certain type de question, comme l’index à la fin d’un livre. Il accélère les lectures, mais il occupe de l’espace de stockage et doit être mis à jour à chaque écriture : une table dotée de dix index est donc lente pour les insertions. Un cache conserve une copie de la réponse à une question coûteuse dans un endroit rapide, par exemple en mémoire, pour que la personne suivante qui la pose l’obtienne immédiatement. Les caches expliquent pourquoi la page d’un produit populaire se charge vite même quand la base de données derrière est très sollicitée, mais ils soulèvent une question difficile : quand les données d’origine changent, à quelle vitesse la copie doit-elle changer aussi ? Afficher un prix périmé pendant quelques secondes peut être acceptable ; afficher un solde bancaire périmé ne l’est peut-être pas.

La compression est l’échange inverse : dépenser du temps CPU pour tasser les données dans moins d’octets, ce qui économise du stockage et du temps de transfert réseau.

Pourquoi c’est important pour l’architecture

Les architectes écrivent rarement des algorithmes de tri, mais ils prennent sans cesse des décisions dont les conséquences sont exactement celles-ci. À quelles questions le système devra-t-il répondre rapidement, et les données ont-elles les index nécessaires pour y répondre ? Jusqu’où les données auront-elles grossi dans trois ans, et quelles parties de la conception sont linéaires, ou pire, face à cette croissance ? Où la mise en cache vaut-elle sa complexité, et à quel point les données en cache peuvent-elles être périmées ? Quand le volume de données est multiplié par dix, quel composant casse en premier ?

Ce sont des questions de performances et de scalabilité, que le chapitre 2 précise, ainsi que de mise en cache et de choix de base de données, que le chapitre 7 traite en profondeur. La section suivante passe des données au code, et à la façon d’organiser le code pour que des personnes puissent le comprendre et le modifier.