“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 207 — #217
i
i
i
i
i
i
i
i
4.3 Les flots
207
Il s’appelle alors récursivement sur le flot d’éléments restants. La figure 4.11 donne
une illustration. Cette figure étend la notation graphique avec un autre élément, le
triangle, qui représente la décomposition ou la construction d’un flot à partir d’un
premier élément et un autre flot. Voici la définition du crible (« sieve » en anglais) :
fun {Sieve Xs}
case Xs of nil then nil
[] X|Xr then Ys in
thread Ys={Filter Xr
fun {$ Y} Y mod X \= 0 end} end
X|{Sieve Ys}
end
end
Cette définition est assez simple, étant donné qu’elle installe un pipeline d’activités
concurrentes. Voici un appel du crible :
local Xs Ys in
thread Xs={Generate 2 100000} end
thread Ys={Sieve Xs} end
{Browse Ys}
end
Sieve
X|Zs
Xs
Xr
X
Ys
Zs
Sieve
Filter
Figure 4.11 Un crible de nombres premiers implémenté avec des flots.
Ce programme affiche les nombres premiers jusqu’à 100 000. Il est un peu simpliste parce qu’il crée trop de fils, à savoir un par nombre premier. Un nombre de
fils tellement grand n’est pas nécessaire. Il est facile de voir que la génération de
nombres premiers jusqu’à n ne nécessite le filtrage de multiples que jusqu’à
√
n.
4
Nous modifions le programme pour arrêter la création des filtres après cette limite :
4. Si le facteur f est plus grand que
√
n, il y aura un autre facteur n/ f plus petit que
√
n.
© Dunod – La photocopie non autorisée est un délit