Jednoprůchodový algoritmus - One-pass algorithm
V práci na počítači, algoritmus jednoprůchodový nebo jednoprůchodový algoritmus je streamování algoritmus , který čte svůj vstup právě jednou. Činí tak zpracováním položek v pořádku, bez neomezeného ukládání do vyrovnávací paměti ; načte blok do vstupní vyrovnávací paměti , zpracuje ji a přesune výsledek do výstupní vyrovnávací paměti pro každý krok procesu. Jednoprůchodový algoritmus obecně vyžaduje čas O ( n ) (viz „velká O“ notace ) a méně než úložiště O ( n ) (obvykle O (1)), kde n je velikost vstupu. Příkladem jednoprůchodového algoritmu je Sondikův částečně pozorovatelný Markovův rozhodovací proces .
Ukázkové problémy řešitelné jednoprůchodovými algoritmy
Vzhledem k jakémukoli seznamu jako vstupu:
- Spočítejte počet prvků.
Vzhledem k seznamu čísel:
- Najděte k největší nebo nejmenší prvky, k dané předem.
- Najděte součet , průměr , rozptyl a směrodatnou odchylku prvků seznamu. Viz také Algoritmy pro výpočet rozptylu .
Dostanete seznam symbolů z abecedy k symbolů, uvedených předem.
- Spočítejte, kolikrát se každý symbol objevil na vstupu.
- Najděte nejvíce nebo nejméně časté prvky.
- Seřadit seznam podle určitého pořadí na symbolech (možné, protože počet symbolů je omezený).
- Najděte maximální mezeru mezi dvěma vzhledy daného symbolu.
Ukázkové problémy neřešitelné jednoprůchodovými algoritmy
Vzhledem k jakémukoli seznamu jako vstupu:
- Najděte n- tý prvek od konce (nebo načtěte, že seznam obsahuje méně než n prvků).
- Najděte prostřední prvek seznamu. To je však řešitelné dvěma průchody: Průchod 1 počítá prvky a průchod 2 vybírá prostřední.
Vzhledem k seznamu čísel:
- Najděte medián .
- Najděte režimy (To není totéž jako najít nejčastější symbol z omezené abecedy).
- Seřadit seznam.
- Počítat počet položek větší nebo menší než průměr . To však lze provést v konstantní paměti dvěma průchody: Průchod 1 najde průměr a průchod 2 počítá.
Výše uvedené dvouprůchodové algoritmy jsou stále streamovacími algoritmy, ale ne jednoprůchodovými.
Reference
- ^ Schweikardt, Nicole. „One-Pass Algorithm“ (PDF) . Citováno 2021-07-01 .
- ^ Pollett, Chris (2005-03-14). „Jedno a dvouprůchodové algoritmy“ (PDF) . Citováno 2021-07-01 .
- ^ Schweikardt, Nicole (2009), LIU, LING; ÖZSU, M. TAMER (eds.), „One-Pass Algorithm“ , Encyclopedia of Database Systems , Boston, MA: Springer USA, str. 1948–1949, doi : 10,1007 / 978-0-387-39940-9_253 , ISBN 978-0-387-39940-9, vyvoláno 2021-04-13
- ^ „Sondikův jednoprůchodový algoritmus“ . www.pomdp.org .
 |
Tento článek o informatice je útržek . Wikipedii můžete pomoci rozšířením . |