Náhodný přístup - Random access

Náhodný přístup ve srovnání se sekvenčním přístupem

Náhodný přístup (přesněji a obecněji nazývaný přímý přístup ) je schopnost přistupovat k libovolnému prvku sekvence ve stejném čase nebo k libovolnému údaji z populace adresovatelných prvků zhruba stejně snadno a efektivně jako kterýkoli jiný, bez ohledu na to, kolik prvků může být být v sadě. Ve vědě o počítačích se obvykle porovnává se sekvenčním přístupem, který vyžaduje načtení dat v pořadí, v jakém byly uloženy.

Například data mohou být uložena teoreticky v jedné sekvenci jako řádek, ve dvou dimenzích, jako jsou řádky a sloupce na povrchu, nebo ve více dimenzích. Avšak vzhledem ke všem souřadnicím může program přistupovat ke každému záznamu přibližně stejně rychle a snadno jako kdokoli jiný. V tomto smyslu je volba vztažného bodu libovolná v tom smyslu, že bez ohledu na to, která položka je hledána, k nalezení je potřeba pouze její adresa, tj. Souřadnice, na kterých se nachází, například jeho řádek a sloupec (nebo jeho číslo záznamu a záznamu na magnetickém bubnu ). Nejprve byl použit termín „náhodný přístup“, protože tento proces musel být schopen najít záznamy bez ohledu na to, v jakém pořadí byly požadovány. Brzy si však výraz „přímý přístup“ získal přízeň, protože bylo možné záznam přímo získat, bez ohledu na to, jaká je jeho pozice. Funkčním atributem však je, že zařízení může přistupovat k libovolnému požadovanému záznamu okamžitě na vyžádání. Opakem je sekvenční přístup , kde vzdálenému prvku trvá přístup déle.

Typickým příkladem tohoto rozlišení je porovnání starodávného svitku (sekvenčního; veškerý materiál před potřebnými daty musí být rozvinut) a knihy (přímý: lze jej okamžitě otočit na libovolnou stránku ). Modernějším příkladem je kazetový magnetofon (sekvenční - jeden se musí rychle posunout vpřed skrz dřívější skladby, aby se dostal k pozdějším) a CD (přímý přístup - lze přeskočit na požadovanou stopu s vědomím, že to bude ta, která byla získána).

V datových strukturách přímý přístup implikuje schopnost přistupovat k libovolným položkám v seznamu v konstantním čase (nezávisle na jeho poloze v seznamu a na velikosti seznamu). Velmi málo datových struktur může zajistit tuto záruku kromě polí (a souvisejících struktur, jako jsou dynamická pole ). Přímý přístup je vyžadován nebo přinejmenším cenný v mnoha algoritmech, jako je binární vyhledávání , třídění celých čísel nebo některé verze síta Eratosthenes .

Jiné datové struktury, jako jsou propojené seznamy , obětují přímý přístup, aby umožnily efektivní vkládání, mazání nebo nové uspořádání dat. Samovyvažující binární vyhledávací stromy mohou poskytnout přijatelný kompromis, kdy přístupový čas není stejný pro všechny členy kolekce, ale maximální čas na načtení daného člena roste pouze logaritmicky s jeho velikostí.

Reference

Viz také