Algoritmo de una sola pasada

Tipo de algoritmo de streaming

En informática, un algoritmo de un solo paso o algoritmo de paso único es un algoritmo de transmisión que lee su entrada exactamente una vez. ^[1] Lo hace procesando los elementos en orden, sin almacenamiento en búfer ilimitado ; lee un bloque en un búfer de entrada , lo procesa y mueve el resultado a un búfer de salida para cada paso del proceso. ^[2] Un algoritmo de un solo paso generalmente requiere O ( n ) (ver notación 'O grande' ) tiempo y menos de O ( n ) almacenamiento (normalmente O (1)), donde n es el tamaño de la entrada. ^[3] Un ejemplo de un algoritmo de un solo paso es el proceso de decisión de Markov parcialmente observable de Sondik . ^[4]

Ejemplos de problemas solucionables mediante algoritmos de una sola pasada

Dada cualquier lista como entrada:

• Cuente el número de elementos.

Dada una lista de números:

• Encuentra los k elementos más grandes o más pequeños, k dados de antemano.
• Halla la suma , la media , la varianza y la desviación estándar de los elementos de la lista. Consulta también Algoritmos para calcular la varianza .

Dada una lista de símbolos de un alfabeto de k símbolos, dado de antemano.

• Cuente el número de veces que aparece cada símbolo en la entrada.
• Encuentra los elementos más o menos frecuentes.
• Ordene la lista según algún orden en los símbolos (es posible ya que el número de símbolos y después es limitado).
• Encuentra la brecha máxima entre dos apariciones de un símbolo dado.

Ejemplos de problemas que no se pueden resolver con algoritmos de una sola pasada

Dada cualquier lista como entrada:

• Encuentra el n -ésimo elemento desde el final (o informa que la lista tiene menos de n elementos).
• Encuentra el elemento del medio de la lista. Sin embargo, esto se puede resolver con dos pasadas: la pasada 1 cuenta los elementos y la pasada 2 selecciona el del medio.

Dada una lista de números:

• Encuentra la mediana .
• Encuentra los modos (esto no es lo mismo que encontrar el símbolo más frecuente de un alfabeto limitado).
• Ordenar la lista.
• Cuente la cantidad de elementos mayores o menores que la media . Sin embargo, esto se puede hacer en la memoria constante con dos pasadas: la pasada 1 encuentra la media y la pasada 2 hace el recuento.

Los algoritmos de dos pasadas anteriores siguen siendo algoritmos de transmisión , pero no algoritmos de una sola pasada.

Referencias

1. Schweikardt, Nicole. "Algoritmo de una sola pasada" (PDF) . Consultado el 1 de julio de 2021 .
2. Pollett, Chris (14 de marzo de 2005). "Algoritmos de uno y dos pasos" (PDF) . Consultado el 1 de julio de 2021 .
3. Schweikardt, Nicole (2009), "One-Pass Algorithm", en LIU, LING ; ÖZSU, M. TAMER (eds.), Encyclopedia of Database Systems , Boston, MA: Springer US, págs. 1948-1949, doi :10.1007/978-0-387-39940-9_253, ISBN 978-0-387-39940-9, consultado el 13 de abril de 2021
4. "Algoritmo de una sola pasada de Sondik". www.pomdp.org .