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:

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

  1. ^ Schweikardt, Nicole. "Algoritmo One-Pass" (PDF) . Obtido em 2021-07-01 .
  2. ^ Pollett, Chris (2005-03-14). "Algoritmos de um e dois passes" (PDF) . Obtido em 2021-07-01 .
  3. ^ 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
  4. ^ "Algoritmo One-Pass de Sondik" . www.pomdp.org .