Leçon 24 : Scan parallèle (somme de préfixes) — l'idée
Un scan, ou somme de préfixes, transforme un tableau en la séquence de ses sommes cumulées. Dans un scan inclusif, la sortie à la position i est la somme de tous les éléments de 0 à i inclus : output[i] = in[0] + in[1] + ... + in[i]. Par exemple, [3,1,2,4] devient [3,4,6,10]. Il existe aussi une var
Imagine une file de personnes, chacune avec un nombre, et chacune doit finir avec la somme de tous ceux qui la précèdent, elle-même comprise. Au lieu de chuchoter de voisin en voisin lentement, à chaque tour chacune ajoute le nombre de la personne un pas à sa gauche, puis deux pas, puis quatre. Les sauts doublent — et toute la file termine en quelques tours.
- somme de préfixes (prefix sum / scan)
- Transformer un tableau en ses sommes cumulées. Dans un scan inclusif, output[i] est la somme de in[0..i] inclus.
- inclusif contre exclusif (inclusive vs exclusive)
- Inclusif : chaque sortie inclut l'élément à sa position ([3,1,2,4]->[3,4,6,10]). Exclusif : commence à zéro et se décale vers la droite ([0,3,4,6]).
- l'idée du doublement (doubling)
- À chaque tour, chaque élément s'ajoute le voisin situé à une distance d, et d double (1,2,4,...). Après log2(n) tours, chaque position a accumulé tous ses prédécesseurs.
- somme cumulée (running total)
- La somme accumulée jusqu'à un point donné. La version séquentielle la calcule dans une boucle en O(n) étapes.
