Traiter en flux
Ce que ce chapitre apporte 5 points
- É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, elle, oblige à garder des valeurs à mesure qu'elles arrivent, 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 variance se calcule en retenant trois nombres. 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.
Qu'est-ce qu'un traitement à mémoire bornée ?
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 : la figure la calcule en gardant tout, faute de savoir quelle valeur se trouvera au milieu avant d'avoir vu la dernière. Sur ces données, qui répètent six valeurs, un compteur par valeur distincte suffirait, comme pour le décompte ; sur des valeurs toutes différentes, dans un flux dont la longueur n'est pas connue d'avance, rien ne permet de faire mieux. 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 : accepter une erreur de quelques pour cent pour ramener la mémoire de plusieurs gigaoctets à quelques kilooctets. L'algorithme HyperLogLog, publié en 2007, estime ainsi plus d'un milliard de valeurs distinctes à 2 % près avec un kilooctet et demi. Le parcours ne le déroule pas : il suffit ici de savoir qu'il existe, et ce qu'il en coûte de renoncer à l'exactitude.
Le piège se vérifie sur une donnée dont la longueur et la variété se règlent : la figure suivante tire ses valeurs au hasard, à graine fixe, parmi un nombre de valeurs différentes que l'on choisit, et suit la mémoire de cinq calculs.
À 400 lignes, porter « valeurs différentes » à 1 000 : sans une ligne de plus, le décompte monte à 328 cases ; à 10 000, il atteint 390 cases, presque une par ligne.
Décocher distinct et mediane : l'échelle s'arrête à 3 cases, et les trois courbes restent plates, quelle que soit la position des deux curseurs.
Parmi ces calculs, lequel n'est pas décomposable ?
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.
Welford calcule la même chose, sans accumuler de grandes sommes. 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.
Il soustrait lui aussi deux nombres proches, x - moyenne, mais ces deux nombres sont connus à l'arrondi de leur dernier chiffre près : leur différence est exacte, ou presque. La formule des accumulateurs soustrait deux sommes de carrés qui ont déjà perdu leurs derniers chiffres dans l'arrondi, et la soustraction ne fait que révéler cette perte. C'est la règle générale du calcul en virgule flottante : soustraire deux nombres proches ne détruit rien par soi-même, cela met à nu l'erreur qu'ils portaient déjà. Il faut donc réorganiser le calcul pour ne pas accumuler de grandes quantités arrondies.
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 qui met l'erreur à nu, puis de réorganiser le calcul qui la précède.
1.La formule « moyenne des carrés moins carré de la moyenne » sur des valeurs autour de 10⁹…
2.vues = set() alimenté ligne par ligne est-il à mémoire bornée ?
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.
Pourquoi un générateur ne se lit-il qu'une fois ?
Quand le calcul n'admet pas de forme en une passe
Trois issues, dans l'ordre où il faut les envisager.
Reformuler, relire, ou approcher. 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 six accumulateurs, le compte, les deux sommes, les deux sommes de carrés et la somme des produits.
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. Ces algorithmes approchés, HyperLogLog pour les distincts ou les résumés de quantiles pour la médiane, sont nommés ici sans être déroulés.
L'ordre compte. Chercher à approcher un calcul qui admet une forme exacte en une passe revient à perdre de la précision pour rien.
Un calcul n'admet pas de forme en une passe. Que tenter en premier ?
Mettre en pratique
Un traitement en flux se juge à une seule quantité : la taille de son état. Elle décide s'il tiendra sur un milliard de valeurs ou s'il s'effondrera bien avant.
Chiffrer l'état d'un traitement en une passe
- 1.
Combien de nombres faut-il retenir pour calculer une moyenne en une seule lecture ?
- 2.
Combien en faut-il pour calculer aussi la variance dans la même passe ?
- 3.
Un flux compte un milliard de valeurs. De combien de nombres l'état d'une moyenne grossit-il quand on passe d'un million à un milliard de valeurs ?
- 4.
Un flux de valeurs toutes différentes arrive, sans que sa longueur soit connue d'avance. Juste après la lecture de la 1 000e valeur, combien de valeurs faut-il garder pour pouvoir encore donner la médiane exacte, quelle que soit la suite ?
La question qui classe un calcul. « Mon état grossit-il avec les données ? » Si la réponse est non, le calcul tient sur n'importe quel volume, sur une machine ordinaire, et il tient indéfiniment. Si la réponse est oui, il ne tient que jusqu'à un certain point, et ce point arrive toujours plus tôt que prévu.
Entre les deux, il existe une famille de réponses approchées à état borné, qui donnent une médiane ou un compte de valeurs distinctes à quelques pour cent près. Renoncer à l'exactitude est souvent le seul moyen de rester en une passe, et c'est un choix à écrire, pas à subir.
Écrire, en une passe et en mémoire bornée, un traitement qui donne la moyenne et la variance d'une suite de mesures.
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. L'écart type s'en déduit à la fin, par une racine carrée de la variance : il ne demande aucun état de plus.
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 ?
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.
Ce code est-il en mémoire bornée ?
Le corrigé
Cela dépend entièrement du nombre de valeurs différentes que prend cle, et pas du tout du nombre de lignes.
Sur des villes, le dictionnaire ne dépassera jamais le nombre de communes, un peu moins de trente-cinq mille en France ; ici, cinq entrées pour cinquante mille lignes. 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 : cinquante mille entrées pour cinquante mille 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 ? ».
Chapitre révisé en octobre 2026 · Une erreur dans ce chapitre ?
Dans la bibliothèque d'exercices
Ce qu'un calcul peut retenir quand le flux ne s'arrête jamais.
- Ce qu'un calcul en flux peut retenirNiveau 2
- Un générateur qui ne se relit pasNiveau 2
- Calculer une moyenne sans tout garderNiveau 2
- Une variance en une passe, qui tient sur de grands nombresNiveau 3