Sekvenční přístup

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search
Sekvenční přístup v porovnání s přímým přístupem.

Sekvenční přístup v matematické informatice znamená, že sada prvků (například pole v paměti nebo soubor na disku) se zpracovává v předem určeném pořadí. Některé datové struktury nebo paměťová zařízení umožňují jenom sekvenční přístup; příkladem je jednosměrný spojový seznam nebo soubor na magnetické pásce. U některých datových struktur je sekvenční přístup jen jednou z přístupových metod, kterou lze použít, pokud zpracování posloupnosti datových prvků po řadě postačuje[1].

O datové struktuře řekneme, že umožňuje sekvenční přístup, jestliže lze v ní obsažené hodnoty projít všechny v určitém pořadí. Typickým příkladem je spojový seznam. Naopak struktury používající hašování obvykle sekvenční přístup neumožňují. Algoritmy, kterým nestačí sekvenční přístup, si mohou k urychlení přístupu vytvořit index. Indexování seznamu, ke kterému lze přistupovat pouze sekvenčně, má asymptotickou složitost O(k), kde k je počet prvků seznamu, což může způsobit, že algoritmy, které jsou založené na přímém přístupu, degenerují na pomalé algoritmy, které mohou být méně efektivní než jejich naivní alternativy; příkladem je quicksort a binární vyhledávání. Na druhou stranu existují algoritmy, jejichž efektivitu omezení na sekvenční přístup nesníží. Příkladem je mergesort.

Je třeba poněkud rozlišovat, zda chceme projít všechny prvky a nezáleží nám na pořadí (v pseudokódu for each) nebo chceme prvky projít v určeném pořadí nebo systém dovoluje průchod daty pouze v nějakém pořadí. To první dokážeme i v hašovací tabulce. To druhé je těžší a zcela běžná 9 z 10 databází metoda je výše popsaný index. V něm jsou pak listové stránky propojeny pointry, které umožní rychlý sekvenční průchod v požadovaném pořadí. A abychom se o to už vůbec nemuseli starat, necháme to na na návrhový vzor iterátor nebo něco s podobnou funkcionalitou. To třetí je obvyklý, přesněji původní význam pojmu sekvenční přístup se všemi důsledky.

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Sequential access na anglické Wikipedii.

  1. Random and Sequential Data Access Na webu TechNet