Algorithme en un seul passage - One-pass algorithm
En informatique, un algorithme à un seul passage ou un algorithme à un seul passage est un algorithme de streaming qui lit son entrée exactement une fois. Il le fait en traitant les éléments dans l'ordre, sans mise en mémoire tampon illimitée ; il lit un bloc dans un tampon d'entrée , le traite et déplace le résultat dans un tampon de sortie pour chaque étape du processus. Un algorithme à une passe nécessite généralement O ( n ) (voir notation 'grand O' ) et moins de O ( n ) stockage (généralement O (1)), où n est la taille de l'entrée. Un exemple d'algorithme à une passe est le processus de décision de Markov partiellement observable de Sondik .
Exemples de problèmes pouvant être résolus par des algorithmes en une seule passe
Étant donné une liste en entrée :
- Comptez le nombre d'éléments.
Étant donné une liste de nombres :
- Trouvez les k éléments les plus grands ou les plus petits, k donnés à l'avance.
- Trouvez la somme , la moyenne , la variance et l' écart type des éléments de la liste. Voir aussi Algorithmes de calcul de la variance .
Étant donné une liste de symboles d'un alphabet de k symboles, donnée à l'avance.
- Comptez le nombre de fois où chaque symbole apparaît dans l'entrée.
- Trouvez les éléments les plus ou les moins fréquents.
- Triez la liste selon un certain ordre sur les symboles (possible car le nombre de symboles est limité).
- Trouver l'écart maximum entre deux apparitions d'un symbole donné.
Exemples de problèmes non résolvables par des algorithmes en un seul passage
Étant donné une liste en entrée :
- Trouvez le n ième élément à partir de la fin (ou signalez que la liste contient moins de n éléments).
- Trouvez l'élément du milieu de la liste. Cependant, cela peut être résolu en deux passes : la passe 1 compte les éléments et la passe 2 sélectionne celui du milieu.
Étant donné une liste de nombres :
- Trouvez la médiane .
- Trouvez les modes (Ce n'est pas la même chose que de trouver le symbole le plus fréquent dans un alphabet limité).
- Triez la liste.
- Comptez le nombre d'éléments supérieur ou inférieur à la moyenne . Cependant, cela peut être fait en mémoire constante avec deux passes : la passe 1 trouve la moyenne et la passe 2 fait le comptage.
Les algorithmes à deux passes ci-dessus sont toujours des algorithmes de streaming mais pas des algorithmes à une passe.
Les références
- ^ Schweikardt, Nicole. "Algorithme en un seul passage" (PDF) . Récupéré le 2021-07-01 .
- ^ Pollett, Chris (2005-03-14). « Algorithmes à un et deux passages » (PDF) . Récupéré le 2021-07-01 .
- ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (eds.), "One-Pass Algorithm" , Encyclopedia of Database Systems , Boston, MA: Springer US, pp. 1948-1949, doi : 10.1007/978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, récupéré le 2021-04-13
- ^ "Algorithme à un passage de Sondik" . www.pomdp.org .