Losowy dostęp - Random access
Dostęp losowy (dokładniej i bardziej ogólnie nazywany dostępem bezpośrednim ) to możliwość dostępu do dowolnego elementu sekwencji w równym czasie lub do dowolnego punktu odniesienia z populacji elementów adresowalnych z grubsza tak samo łatwo i wydajnie jak każdy inny, bez względu na to, ile elementów może być w zestawie. W informatyce jest to zwykle przeciwstawne dostępowi sekwencyjnemu, który wymaga pobierania danych w kolejności ich przechowywania.
Na przykład dane mogą być przechowywane hipotetycznie w jednej sekwencji, takiej jak wiersz, w dwóch wymiarach, takich jak wiersze i kolumny na powierzchni, lub w wielu wymiarach. Jednak biorąc pod uwagę wszystkie współrzędne, program może uzyskać dostęp do każdego rekordu tak szybko i łatwo, jak każdy inny. W tym sensie wybór punktu odniesienia jest arbitralny w tym sensie, że bez względu na to, który element jest poszukiwany, wszystko, co jest potrzebne, aby go znaleźć, to jego adres, czyli współrzędne, pod którymi się znajduje, takie jak wiersz i kolumna (lub jego numer utworu i rekordu na bębnie magnetycznym ). Początkowo używano terminu „dostęp losowy”, ponieważ proces musiał być w stanie znaleźć rekordy bez względu na to, w jakiej kolejności były wymagane. Jednak wkrótce termin „bezpośredni dostęp” zyskał popularność, ponieważ można było bezpośrednio pobrać zapis, niezależnie od jego pozycji. Jednak atrybutem operacyjnym jest to, że urządzenie może uzyskać dostęp do dowolnego wymaganego rekordu natychmiast na żądanie. Przeciwieństwem jest dostęp sekwencyjny , w którym dostęp do elementu zdalnego zajmuje więcej czasu.
Typową ilustracją tego rozróżnienia jest porównanie starożytnego zwoju (sekwencyjnego; cały materiał przed potrzebnymi danymi musi zostać rozwinięty) i księgi (bezpośrednio: można ją natychmiast otworzyć na dowolnej dowolnej stronie ). Bardziej nowoczesnym przykładem jest kaseta magnetofonowa (sekwencyjna — trzeba szybko przewijać wcześniejsze utwory, aby przejść do późniejszych) i CD (bezpośredni dostęp — można przeskoczyć do żądanego utworu, wiedząc, że będzie to ten, który zostanie pobrany).
W strukturach danych bezpośredni dostęp oznacza możliwość dostępu do dowolnego wpisu na liście w stałym czasie (niezależnie od jego pozycji na liście i rozmiaru listy). Bardzo niewiele struktur danych może zapewnić tę gwarancję, innych niż tablice (i powiązane struktury, takie jak tablice dynamiczne ). Dostęp bezpośredni jest wymagany, a przynajmniej cenny, w wielu algorytmach, takich jak wyszukiwanie binarne , sortowanie liczb całkowitych lub niektóre wersje sita Eratostenesa .
Inne struktury danych, takie jak listy połączone , poświęcają bezpośredni dostęp, aby umożliwić wydajne wstawianie, usuwanie lub zmianę kolejności danych. Samobalansujące drzewa wyszukiwania binarnego mogą zapewnić akceptowalny kompromis, w którym czas dostępu nie jest równy dla wszystkich członków kolekcji, ale maksymalny czas pobrania danego elementu rośnie tylko logarytmicznie wraz z jego rozmiarem.
Bibliografia
Zobacz też
- Strumień danych
- Maszyna o dostępie swobodnym
- Pamięć o dostępie swobodnym, chociaż pamięć podręczna i pamięć wirtualna sprawiają, że nie jest to już prawdziwie losowy dostęp.
- Miejscowość odniesienia
