Sekvenční přístup

Technology

12 hours ago

Author

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.

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. +more 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 řadící algoritmus rychlé řazení a binární vyhledávání. Na druhou stranu existují algoritmy, jejichž efektivitu omezení na sekvenční přístup nesníží. Příkladem je algoritmus řazení slučováním.

Je třeba poněkud rozlišovat, zda chceme projít všechny prvky a nezáleží nám na pořadí 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. +more 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 ukazateli, 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 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.