Algorytm jednoprzebiegowy - One-pass algorithm
W obliczeniach algorytm jednoprzebiegowy lub algorytm jednoprzebiegowy to algorytm przesyłania strumieniowego, który odczytuje dane wejściowe dokładnie raz. Robi to, przetwarzając elementy w kolejności, bez nieograniczonego buforowania ; wczytuje blok do bufora wejściowego , przetwarza go i przenosi wynik do bufora wyjściowego dla każdego kroku procesu. Algorytm jednoprzebiegowy zazwyczaj wymaga czasu O ( n ) (patrz notacja 'duże O' ) i mniej niż O ( n ) pamięci (zazwyczaj O (1)), gdzie n jest rozmiarem danych wejściowych. Przykładem algorytmu jednoprzebiegowego jest częściowo obserwowalny proces decyzyjny Markowa Sondika .
Przykładowe problemy rozwiązywalne algorytmami jednoprzebiegowymi
Biorąc pod uwagę dowolną listę jako dane wejściowe:
- Policz liczbę elementów.
Biorąc pod uwagę listę liczb:
- Znajdź k największych lub najmniejszych elementów, k podanych z góry.
- Znajdź sumę , średnią , wariancję i odchylenie standardowe elementów listy. Zobacz także Algorytmy obliczania wariancji .
Dana lista symboli z alfabetu k symboli, podana z góry.
- Policz, ile razy każdy symbol pojawia się na wejściu.
- Znajdź najczęstsze lub najrzadziej występujące elementy.
- Posortuj listę według kolejności symboli (możliwe, ponieważ liczba symboli jest ograniczona).
- Znajdź maksymalną przerwę między dwoma wystąpieniami danego symbolu.
Przykładowe problemy nierozwiązywalne przez algorytmy jednoprzebiegowe
Biorąc pod uwagę dowolną listę jako dane wejściowe:
- Znajdź n- ty element od końca (lub zgłoś, że lista ma mniej niż n elementów).
- Znajdź środkowy element listy. Można to jednak rozwiązać za pomocą dwóch przejść: Przebieg 1 liczy elementy, a Przebieg 2 wybiera środkowy.
Biorąc pod uwagę listę liczb:
- Znajdź medianę .
- Znajdź tryby (to nie to samo, co znalezienie najczęstszego symbolu z ograniczonego alfabetu).
- Posortuj listę.
- Policz liczbę elementów większą lub mniejszą od średniej . Można to jednak zrobić w stałej pamięci z dwoma przebiegami: Przebieg 1 wyznacza średnią, a przebieg 2 liczy.
Powyższe algorytmy dwuprzebiegowe są nadal algorytmami przesyłania strumieniowego, ale nie jednoprzebiegowymi.
Bibliografia
- ^ Schweikardt, Nicole. „Algorytm jednoprzebiegowy” (PDF) . Pobrano 2021-07-01 .
- ^ Pollett, Chris (2005-03-14). „Algorytmy jedno- i dwuprzebiegowe” (PDF) . Pobrano 2021-07-01 .
- ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (red.), "Algorytm jednoprzebiegowy " , Encyklopedia systemów baz danych , Boston, MA: Springer US, s. 1948-1949, doi : 10.1007/978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, pobrano 2021-04-13
- ^ „Algorytm jednoprzebiegowy Sondika” . www.pomdp.org .