Algoritmo de uma passagem - One-pass algorithm
Na computação, um algoritmo de passagem única ou algoritmo de passagem única é um algoritmo de streaming que lê sua entrada exatamente uma vez. Ele faz isso processando os itens em ordem, sem buffer ilimitado ; ele lê um bloco em um buffer de entrada , processa-o e move o resultado para um buffer de saída para cada etapa do processo. Um algoritmo de uma passagem geralmente requer tempo O ( n ) (ver notação 'big O' ) e menos do que O ( n ) armazenamento (normalmente O (1)), onde n é o tamanho da entrada. Um exemplo de algoritmo de uma passagem é o processo de decisão de Markov parcialmente observável de Sondik .
Problemas de exemplo solucionáveis por algoritmos de uma passagem
Dada qualquer lista como entrada:
- Conte o número de elementos.
Dada uma lista de números:
- Encontre os k maiores ou menores elementos, k dados antecipadamente.
- Encontre a soma , média , variância e desvio padrão dos elementos da lista. Consulte também Algoritmos para calcular a variância .
Dada uma lista de símbolos de um alfabeto de k símbolos, fornecida antecipadamente.
- Conte o número de vezes que cada símbolo aparece na entrada.
- Encontre os elementos mais ou menos frequentes.
- Classifique a lista de acordo com alguma ordem nos símbolos (possível, pois o número de símbolos é limitado).
- Encontre o intervalo máximo entre duas aparências de um determinado símbolo.
Problemas de exemplo não solucionáveis por algoritmos de uma passagem
Dada qualquer lista como entrada:
- Encontrar o n ésimo elemento a partir da extremidade (ou relatório que a lista que tem menos de n elementos).
- Encontre o elemento do meio da lista. No entanto, isso pode ser resolvido com duas passagens: a passagem 1 conta os elementos e a passagem 2 seleciona o do meio.
Dada uma lista de números:
- Encontre a mediana .
- Encontre os modos (isso não é o mesmo que encontrar o símbolo mais frequente em um alfabeto limitado).
- Classifique a lista.
- Conte o número de itens maior ou menor que a média . No entanto, isso pode ser feito na memória constante com duas passagens: a passagem 1 encontra a média e a passagem 2 faz a contagem.
Os algoritmos de duas passagens acima ainda são algoritmos de streaming, mas não algoritmos de uma passagem.
Referências
- ^ Schweikardt, Nicole. "Algoritmo One-Pass" (PDF) . Obtido em 2021-07-01 .
- ^ Pollett, Chris (2005-03-14). "Algoritmos de um e dois passes" (PDF) . Obtido em 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, recuperado em 2021-04-13
- ^ "Algoritmo One-Pass de Sondik" . www.pomdp.org .