Traiter en flux
Ce que ce chapitre apporte
- Écrire un traitement en une passe et savoir dire ce qu'il retient.
- Classer un calcul selon que son état reste borné ou grossit avec les données.
- Calculer somme, moyenne et variance en une seule lecture, sans stocker les valeurs.
- Reconnaître les calculs qui n'admettent pas de forme en une passe, et savoir quoi faire à la place.
- Utiliser les générateurs de Python pour composer des traitements en flux.
Lire une ligne, mettre à jour un état, oublier la ligne. Le motif tient en une phrase et règle le mur de la mémoire quel que soit le volume, à une condition : que le calcul demandé s'en accommode. Or la frontière ne se devine pas. Une somme, une moyenne et même une variance tiennent dans trois cases quelle que soit la taille du fichier. Une médiane exige d'avoir tout gardé, et un décompte de valeurs distinctes aussi.
Le chapitre précédent s'est terminé sur une question : ce traitement peut-il se faire en une seule lecture ? Elle commande presque tout, parce qu'un traitement en une passe à mémoire bornée ne rencontre jamais le mur de la mémoire, s'applique indifféremment à un fichier ou à un flux qui ne s'arrête pas, et se répartit sans difficulté sur plusieurs machines.
Répondre à cette question demande de regarder non pas les données mais ce que le calcul doit retenir. C'est l'objet de ce chapitre.
Le motif, et ce qu'il exige
Un traitement est en une passe s'il lit chaque élément une fois et une seule, dans l'ordre où il arrive, sans jamais revenir en arrière.
Il est de plus à mémoire bornée si la taille de son état ne dépend pas du nombre d'éléments lus. Un traitement en une passe à mémoire bornée traite un fichier de mille lignes et un fichier de mille milliards de lignes avec exactement la même occupation mémoire.
Le motif s'écrit toujours de la même façon : un état initialisé avant la boucle, mis à jour à chaque élément, et lu après.
Trois variables, et elles resteront trois quel que soit le nombre de mesures. C'est cela, une mémoire bornée : non pas « peu de mémoire », mais une quantité de mémoire qui ne dépend pas de la taille des données.
Ajouter valeurs.append(x) dans la boucle, pour « garder les données au cas où », suffit à faire passer le traitement de mémoire bornée à mémoire proportionnelle aux données. Le programme continue de fonctionner, donne le même résultat, et cesse de fonctionner au premier fichier trop gros.
Le même effet se produit avec un print qui accumule dans une chaîne, un journal qui garde chaque ligne traitée, ou un dictionnaire indexé par un identifiant unique. Ce dernier cas est le plus insidieux, parce qu'il ressemble à un état borné et n'en est pas un.
Ce qui tient dans quelques cases
La figure suivante simule la lecture, valeur par valeur, et relève à chaque fois le nombre de cases que le calcul doit garder.
Trois droites horizontales, à une, deux et trois cases. Rien ne monte, et rien ne montera : ajouter un million de valeurs ne changerait pas la hauteur des courbes, seulement leur longueur.
Le cas de la variance mérite qu'on s'y arrête, parce que la plupart des gens la croient impossible en une passe. La définition usuelle demande en effet de connaître la moyenne pour calculer les écarts, donc d'avoir tout lu, donc de tout garder. Mais l'identité qui suit change la donne :
La moyenne des carrés moins le carré de la moyenne donne la variance :
variance = (somme des x²) / n − ((somme des x) / n)²
Trois accumulateurs suffisent donc : le compte n, la somme des valeurs, la somme des carrés. Aucune valeur n'a besoin d'être conservée.
Cette forme s'appelle parfois la formule « des accumulateurs », et elle a un défaut sérieux que la section suivante met à nu.
Ce qui exige de tout garder
Les mêmes données, avec trois calculs d'une autre nature.
Trois régimes se lisent d'un coup d'œil. La moyenne reste plate. La médiane monte tout droit, une case par ligne lue, parce qu'il est impossible de savoir quelle valeur se trouve au milieu avant d'avoir vu la dernière. Le décompte des valeurs distinctes monte aussi, mais s'aplatit à mesure que les valeurs se répètent : il ne retient pas les lignes, il retient les valeurs jamais vues.
Une statistique est décomposable s'il existe un état de taille fixe permettant de la mettre à jour à chaque nouvel élément, et d'en tirer le résultat à la fin.
Somme, compte, moyenne, minimum, maximum, variance, écart type, produit, et toute combinaison de celles-ci sont décomposables.
Médiane, quantiles, nombre de valeurs distinctes, valeur la plus fréquente et médiane pondérée ne le sont pas. Aucun état de taille fixe ne permet de les calculer exactement.
vues = set() puis vues.add(x) a toutes les apparences d'un traitement en flux : une lecture, pas de tri, pas de retour en arrière. Et il l'est bien, en une passe.
Mais sa mémoire n'est pas bornée : elle croît avec le nombre de valeurs différentes. Sur des identifiants d'utilisateurs, des adresses ou des empreintes, ce nombre approche le nombre de lignes, et l'ensemble finit par peser autant que les données.
C'est précisément le problème que résolvent les compteurs approchés, traités plus loin dans le parcours : accepter une erreur de quelques pour cent pour ramener la mémoire de plusieurs gigaoctets à quelques kilo-octets.
La variance en une passe, et son piège numérique
La formule des accumulateurs est juste en arithmétique exacte. Elle ne l'est pas en virgule flottante, et l'échec est spectaculaire.
La formule des accumulateurs soustrait deux nombres de l'ordre de 10¹⁸ dont la différence vaut 8,25. Un flottant sur 64 bits ne retient qu'une quinzaine de chiffres significatifs : à cette échelle, les chiffres qui portaient le résultat ont déjà été perdus dans l'arrondi. Le résultat obtenu n'est pas approximatif, il est arbitraire, et peut même être négatif alors qu'une variance ne l'est jamais.
L'algorithme de Welford maintient la moyenne courante et la somme des écarts au carré, en corrigeant les deux à chaque valeur. Il retient trois nombres, comme la formule des accumulateurs, donc reste à mémoire bornée.
La différence est qu'il ne calcule jamais de grande quantité destinée à être soustraite d'une autre. C'est la règle générale du calcul en virgule flottante : une soustraction entre deux nombres proches et grands détruit l'information, et il faut réorganiser le calcul pour l'éviter plutôt que de la subir.
Une variance négative, un écart type qui vaut zéro sur des données visiblement dispersées, une corrélation légèrement supérieure à 1 : ces trois résultats sont impossibles mathématiquement et signent tous la même cause.
Le réflexe utile n'est pas d'ajouter un max(0, ...) pour masquer le symptôme, mais de chercher la soustraction fautive et de la réécrire.
Les générateurs, l'outil du flux en Python
Une boucle for sur une liste charge la liste. Une boucle for sur un générateur ne charge rien : les valeurs sont produites à la demande, une à la fois.
La dernière ligne surprend toujours et mérite d'être comprise plutôt que contournée : un générateur n'est pas une collection, c'est une lecture en cours. Une fois consommé, il ne reste rien à lire, exactement comme un flux réseau ou un fichier lu jusqu'au bout.
Cette limitation n'est pas un défaut de Python : c'est la réalité de tout traitement en flux, exprimée dans le langage. Les données d'un capteur, d'une file de messages ou d'un fichier volumineux ne se relisent pas gratuitement.
Un traitement qui a besoin de deux lectures doit donc soit relire la source, ce qui coûte, soit être réorganisé pour n'en demander qu'une. La deuxième solution est presque toujours possible quand toutes les statistiques recherchées sont décomposables : il suffit de mettre à jour tous les accumulateurs dans la même boucle.
Les générateurs se composent, et c'est ce qui en fait un outil et non une curiosité. Filtrer, transformer, puis réduire s'écrit en trois étapes dont aucune ne matérialise de collection intermédiaire.
Quand le calcul n'admet pas de forme en une passe
Trois issues, dans l'ordre où il faut les envisager.
Reformuler. Beaucoup de calculs qui semblent exiger deux passes n'en exigent qu'une une fois réécrits. La variance en est l'exemple type. Une corrélation aussi : elle se déduit de cinq accumulateurs.
Relire. Deux passes sur un fichier coûtent deux fois la lecture, ce qui est cher mais fini. C'est acceptable sur des données au repos, et impossible sur un flux qui ne s'arrête pas.
Approcher. Une médiane à 1 % près, un décompte de distincts à 2 % près, les cent valeurs les plus fréquentes : tout cela se calcule en mémoire bornée, à condition d'accepter une erreur dont on connaît la borne. C'est le sujet du chapitre consacré au comptage approché.
L'ordre compte. Chercher à approcher un calcul qui admet une forme exacte en une passe revient à perdre de la précision pour rien.
Exercices type
Exercice 1 : écrire, en une passe et en mémoire bornée, un traitement qui donne la moyenne et l'écart type d'une suite de mesures.
Afficher la solution
Trois accumulateurs suffisent, mis à jour dans la même boucle. En employant Welford plutôt que la formule des accumulateurs, pour les raisons vues plus haut :
programme principal
L'état tient en trois nombres, et ne dépend pas de n. La borne de la boucle est fixée à cinq pour que la figure se déroule ; dans un vrai traitement en flux, la boucle tourne tant qu'une mesure arrive, et rien d'autre ne change. Modifier les valeurs du champ de saisie et redérouler montre que les trois variables suffisent quelle que soit la suite.
Exercice 2 : un traitement doit produire la moyenne, le minimum, le maximum et le nombre de valeurs au-dessus de la moyenne. Combien de passes faut-il ?
Afficher la solution
Deux, et il n'y a pas moyen de faire mieux exactement.
Les trois premières statistiques sont décomposables et se calculent ensemble en une passe. La quatrième ne l'est pas : compter les valeurs au-dessus de la moyenne demande de connaître la moyenne, donc d'avoir tout lu.
Deux issues. Sur des données au repos, relire : la première passe donne la moyenne, la seconde compte. Sur un flux, il faut approcher, par exemple en comptant par rapport à une moyenne glissante plutôt qu'à la moyenne finale, ce qui répond à une question voisine mais différente, et il faut le dire.
Exercice 3 : ce code est-il en mémoire bornée ?
Afficher la solution
Cela dépend entièrement de ville, et pas du tout du nombre de lignes.
Sur les départements français, le dictionnaire ne dépassera jamais une centaine d'entrées : la mémoire est bornée en pratique, quelle que soit la taille du fichier.
Sur des identifiants de session ou des adresses, le nombre de clés distinctes croît avec les lignes : la mémoire n'est pas bornée, et le traitement finira par tomber.
La leçon générale : un dictionnaire est borné par le nombre de clés distinctes, jamais par le nombre de lignes. La question à poser n'est donc pas « combien de lignes ? » mais « combien de clés différentes ? ».
Exercice 4 : pourquoi ce code affiche-t-il zéro pour la seconde somme ?
Afficher la solution
Le premier sum consomme le générateur entièrement. Le second lit un générateur épuisé, ne trouve aucune valeur, et somme sur l'ensemble vide, ce qui donne zéro.
Ce n'est pas une bizarrerie du langage : c'est la propriété d'un flux, et Python la rend visible plutôt que de la masquer. Un fichier lu jusqu'au bout se comporte de la même façon.
Pour lire deux fois, il faut soit reconstruire le générateur, soit matérialiser une liste, ce qui abandonne le bénéfice du flux et doit donc être un choix conscient.
1.Qu'est-ce qu'un traitement à mémoire bornée ?
2.Parmi ces calculs, lequel n'est pas décomposable ?
3.La formule « moyenne des carrés moins carré de la moyenne » sur des valeurs autour de 10⁹…
4.vues = set() alimenté ligne par ligne est-il à mémoire bornée ?
5.Pourquoi un générateur ne se lit-il qu'une fois ?
6.Un calcul n'admet pas de forme en une passe. Que tenter en premier ?
La méthode
- Écrire l'état avant la boucle, et le relire : sa taille dépend-elle du nombre de lignes ?
- Mettre à jour tous les accumulateurs dans la même boucle, pour ne jamais relire sans raison.
- Vérifier chaque collection qui grandit dans la boucle : liste, ensemble, dictionnaire, chaîne.
- Compter les clés distinctes, pas les lignes, dès qu'un dictionnaire est en jeu.
- Employer Welford plutôt que la formule des accumulateurs, dès que les valeurs sont loin de zéro.
- Se méfier de tout résultat impossible : variance négative, corrélation au-dessus de 1, écart type nul.
- Composer avec des générateurs plutôt que des listes intermédiaires.
- Reformuler, puis relire, puis approcher, dans cet ordre et pas un autre.
Synthèse
- Le motif du flux : lire un élément, mettre à jour un état, oublier l'élément.
- Une passe et une mémoire bornée sont deux propriétés distinctes : un traitement peut avoir l'une sans l'autre.
- Une mémoire est bornée quand sa taille ne dépend pas du nombre d'éléments, pas quand elle est petite.
- Sont décomposables : somme, compte, moyenne, minimum, maximum, variance, écart type.
- Ne le sont pas : médiane, quantiles, nombre de valeurs distinctes, valeur la plus fréquente.
- La variance se calcule en une passe avec trois accumulateurs, ce qui surprend et se vérifie.
- La formule des accumulateurs est juste en arithmétique exacte et fausse en virgule flottante dès que les valeurs sont loin de zéro.
- Welford calcule la même chose sans jamais soustraire deux grands nombres presque égaux.
- Un dictionnaire est borné par le nombre de clés distinctes, jamais par le nombre de lignes.
- Un générateur est une lecture en cours et s'épuise, comme tout flux réel.
- Trois issues quand une passe ne suffit pas : reformuler, relire, approcher, dans cet ordre.