Algorytm jednoprzebiegowy

W informatyce algorytm jednoprzebiegowy lub algorytm jednoprzebiegowy to algorytm strumieniowy , który odczytuje dane wejściowe dokładnie raz. Czyni to poprzez przetwarzanie elementów 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 generalnie wymaga O ( n ) (patrz notacja „duże O” ) i pamięci mniejszej niż O ( n ) (zwykle O (1)), gdzie n jest wielkością wejścia. Przykładem algorytmu jednoprzebiegowego jest częściowo obserwowalny proces decyzyjny Markowa Sondika .

Przykładowe problemy rozwiązywane za pomocą algorytmów jednoprzebiegowych

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 .

Biorąc pod uwagę listę symboli z alfabetu k symboli, podaną z góry.

Policz, ile razy każdy symbol pojawia się na wejściu.
Znajdź najczęściej lub najrzadziej występujące elementy.
Posortuj listę zgodnie z kolejnością symboli (jest to możliwe, ponieważ liczba symboli jest ograniczona).
Znajdź maksymalną przerwę między dwoma wystąpieniami danego symbolu.

Przykładowe problemy nierozwiązywalne za pomocą algorytmów jednoprzebiegowych

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 przebiegów: 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ę pozycji większą lub mniejszą od średniej . Można to jednak zrobić w pamięci stałej za pomocą dwóch przebiegów: przebieg 1 znajduje średnią, a przebieg 2 wykonuje liczenie.

Powyższe algorytmy dwuprzebiegowe nadal są algorytmami strumieniowymi , ale nie algorytmami jednoprzebiegowymi.

Bibliografia _ „Algorytm jednoprzebiegowy” (PDF) . Źródło 2021-07-01 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ Pollett, Chris (14.03.2005). „Algorytmy jedno- i dwuprzebiegowe” (PDF) . Źródło 2021-07-01 . {{ cite web }} : CS1 maint: stan adresu URL ( link )
^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (red.), „One-Pass Algorithm” , 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 .

[frankfurt-1] Bibliografia _ „Algorytm jednoprzebiegowy” (PDF) . Źródło 2021-07-01 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[sjsu-2] Pollett, Chris (14.03.2005). „Algorytmy jedno- i dwuprzebiegowe” (PDF) . Źródło 2021-07-01 . {{ cite web }} : CS1 maint: stan adresu URL ( link )

[eds-3] Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (red.), „One-Pass Algorithm” , 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

[pomdp-4] „Algorytm jednoprzebiegowy Sondika” . www.pomdp.org .