![Random vs sequential access](https://upload.wikimedia.org/wikipedia/commons/a/a7/Random_vs_sequential_access.svg)
Random access (more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of
addressable elements roughly as easily and efficiently as any other, no matter how many elements may be in the set. In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
it is typically contrasted to
sequential access
Sequential access is a term describing a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) being accessed in a predetermined, ordered sequence. It is the opposite of random access, the ability to ...
which requires data to be retrieved in the order it was stored.
For example, data might be stored notionally in a single sequence like a row, in two dimensions like rows and columns on a surface, or in multiple dimensions. However, given all the coordinates, a program can access each record about as quickly and easily as any other. In this sense, the choice of datum is arbitrary in the sense that no matter which item is sought, all that is needed to find it is its address, i.e. the coordinates at which it is located, such as its row and column (or its track and record number on a
magnetic drum
Drum memory was a magnetic data storage device invented by Gustav Tauschek in 1932 in Austria. Drums were widely used in the 1950s and into the 1960s as computer memory.
For many early computers, drum memory formed the main working memory ...
). At first, the term "random access" was used because the process had to be capable of finding records no matter in which sequence they were required.
However, soon the term "direct access" gained favour because one could directly retrieve a record, no matter what its position might be.
The operative attribute, however, is that the device can access any required record immediately on demand. The opposite is
sequential access
Sequential access is a term describing a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) being accessed in a predetermined, ordered sequence. It is the opposite of random access, the ability to ...
, where a remote element takes longer time to access.
A typical illustration of this distinction is to compare an ancient
scroll
A scroll (from the Old French ''escroe'' or ''escroue''), also known as a roll, is a roll of papyrus, parchment, or paper containing writing.
Structure
A scroll is usually partitioned into pages, which are sometimes separate sheets of papyrus ...
(sequential; all material prior to the data needed must be unrolled) and the
book
A book is a medium for recording information in the form of writing or images, typically composed of many pages (made of papyrus, parchment, vellum, or paper) bound together and protected by a cover. The technical term for this physical arr ...
(direct: can be immediately flipped open to any arbitrary
page
Page most commonly refers to:
* Page (paper), one side of a leaf of paper, as in a book
Page, PAGE, pages, or paging may also refer to:
Roles
* Page (assistance occupation), a professional occupation
* Page (servant), traditionally a young m ...
). A more modern example is a cassette tape (sequential — one must fast forward through earlier songs to get to later ones) and a
CD (direct access — one can skip to the track wanted, knowing that it would be the one retrieved).
In
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s, direct access implies the ability to access any entry in a
list
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
in
constant time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
(independent of its position in the list and of the list's size). Very few data structures can make this guarantee other than
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
s (and related structures like
dynamic array
In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard lib ...
s). Direct access is required, or at least valuable, in many algorithms such as
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
,
integer sorting
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numb ...
, or certain versions of
sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
.
Other data structures, such as
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
s, sacrifice direct access to permit efficient inserts, deletes, or re-ordering of data.
Self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...
s may provide an acceptable compromise, where access time is not equal for all members of a collection, but the maximum time to retrieve a given member grows only
logarithmically
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
with its size.
References
{{reflist
See also
*
Data stream
In connection-oriented communication, a data stream is the transmission of a sequence of digitally encoded coherent signals to convey information. Typically, the transmitted symbols are grouped into a series of packets.
Data streaming has bec ...
*
Random-access machine
In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the cou ...
*
Random-access memory
Random-access memory (RAM; ) is a form of computer memory that can be read and changed in any order, typically used to store working Data (computing), data and machine code. A Random access, random-access memory device allows data items to b ...
although the
cache
Cache, caching, or caché may refer to:
Places United States
* Cache, Idaho, an unincorporated community
* Cache, Illinois, an unincorporated community
* Cache, Oklahoma, a city in Comanche County
* Cache, Utah, Cache County, Utah
* Cache County ...
and
virtual memory
In computing, virtual memory, or virtual storage is a memory management technique that provides an "idealized abstraction of the storage resources that are actually available on a given machine" which "creates the illusion to users of a very l ...
make this no longer truly random access.
*
Locality of reference
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
Computer memory