Přímý přístup

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Porovnání přímého a sekvenčního přístupu.
Tento článek pojednává o výběru prvku datové struktury, časti souboru nebo paměti. O přístupu do paměti bez účasti procesoru pojednává článek DMA.

Přímý přístup, libovolný přístup, náhodný přístup (anglicky random access nebo direct access) v informatice je možnost přistupovat k jednotlivým prvkům složené datové struktury, časti souboru nebo oblasti paměti v libovolném pořadí podle potřeb zpracování, nikoli podle uložení datové struktury na fyzickém nosiči. Opakem je sekvenční přístup, kdy lze k jednotlivým prvkům přistupovat pouze v tom pořadí, v jakém jsou uloženy na fyzickém nosiči, a přístup k vzdálenému prvku vyžaduje delší čas[1].

Základním vodítkem pro uznání přístupové metody za přímý přístup je, že přístup k prvku musí být stejně snadný a efektivní bez ohledu na jeho umístění, velikost datové struktury a počet souřadnic, které jsou použity pro popis umístění prvku ve struktuře.

Pozice prvku může být například popsána pomocí pořadí v jednoduché posloupnosti, jako je řádek, ve dvourozměrné struktuře, jako jsou řádky a sloupce v rovině, nebo pomocí vícerozměrných souřadnic. Ale po uvedení všech souřadnic, může program přistupovat ke každém záznamu přibližně stejně rychle a snadno jako k libovolnému jinému, a to v čase, který vyhovuje uživateli. V tomto smyslu je volba položky libovolná v tom smyslu, že bez ohledu na to, kterou položku požadujeme, pro její nalezení stačí mít její adresu, neboli souřadnice, na nichž je umístěna, jako například řádek a sloupec (nebo číslo stopy a číslo záznamu na magnetickém bubnu). Termín „náhodný přístup“ byl poprvé použit, když se požadovalo, aby proces našel požadovaný záznam bez ohledu na to, ve kterém místě posloupnosti se nachází[1].

Ale brzy se začal používat termín „přímý přístup“, protože je možné přímo získat záznam bez ohledu na jeho umístění[2]. Funkčním požadavkem je, aby zařízení bylo schopné přistupovat k požadovanému záznamu přímo podle požadavku.

Praktickou ukázkou tohoto rozdílu je porovnání času potřebného pro nalezení místa v textu; pokud je text uložen na svitku, jedná se o sekvenční přístup: celý kus svitku před požadovaným místem musí být převinut; pokud je text v kniha, jedná se o přímý přístup, protože knihu lze otevřít na libovolném místě (jedná se o případ použití záložky; pro nalezení požadované stránky je třeba listovat). Novějším příklad sekvenčního přístupu je magnetofonová kazeta (pokud chceme přehrát skladbu uprostřed, je nutné přetočením pásku přeskočit skladby na začátku) oproti CD (přímý přístup –lze přeskočit přímo na požadovanou kladbu, pokud známe její číslo).

V případě datových struktur znamená přímý přístup možnost získat položku struktury v konstantním čase, nezávislém na pozici ve struktuře a velikosti struktury, tj. v čase O(1). To umožňuje jen málo datových struktur, především pole (a příbuzné struktury jako dynamická pole). Přímý přístup je požadovaný nebo oceňovaný v mnoha algoritmech jako například binární vyhledávání, celočíselné třídění nebo v určitých variantách Eratosthenova síta[3].

Jiné datové struktury jako spojové seznamy přímý přístup neumožňují, ale naopak dovolují efektivní vkládání, rušení nebo přeskupování dat. Samovyvažující se stromy mohou být přijatelným kompromisem, kdy přístupový čas je stejný pro libovolný prvek kolekce, a roste logaritmicky s její velikostí.

Reference[editovat | editovat zdroj]

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

  1. National Computer Conference and Exposition. Proceedings. [s.l.] : [s.n.], 1957. Dostupné online.  
  2. International Business Machines Corporation. Data Processing Division. Introduction to IBM Direct-access Storage Devices and Organization Methods. [s.l.] : International Business Machines Corporation, 1966. Dostupné online.  
  3. D. E. KNUTH. The Art of Computer Programming. Svazek 3. [s.l.] : Addison-Wesley, 1969. Dostupné online. ISBN 978-0-201-03803-3.  

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