Произвольный доступ (точнее и в более общем смысле называемый прямым доступом ) — это возможность доступа к произвольному элементу последовательности за одинаковое время или к любым данным из совокупности адресуемых элементов примерно так же легко и эффективно, как и к любым другим, независимо от того, сколько элементов может быть в наборе. В информатике это обычно противопоставляется последовательному доступу , который требует, чтобы данные извлекались в том порядке, в котором они были сохранены.
Например, данные могут храниться мысленно в одной последовательности, например, в строке, в двух измерениях, например, в строках и столбцах на поверхности, или в нескольких измерениях. Однако, учитывая все координаты, программа может получить доступ к каждой записи примерно так же быстро и легко, как и к любой другой. В этом смысле выбор данных произволен в том смысле, что независимо от того, какой элемент ищется, все, что нужно для его нахождения, — это его адрес, т. е. координаты, по которым он расположен, например, его строка и столбец (или его номер дорожки и записи на магнитном барабане ). Сначала использовался термин «произвольный доступ», поскольку процесс должен был быть способен находить записи независимо от того, в какой последовательности они требовались. [1] Однако вскоре термин «прямой доступ» приобрел популярность, поскольку можно было напрямую извлечь запись, независимо от ее положения. [2] Однако оперативным атрибутом является то, что устройство может получить доступ к любой требуемой записи немедленно по требованию. Противоположностью является последовательный доступ , при котором доступ к удаленному элементу занимает больше времени. [3]
Типичной иллюстрацией этого различия является сравнение древнего свитка (последовательный; весь материал до необходимых данных должен быть развернут) и книги (прямой: может быть немедленно открыт на любой произвольной странице ). Более современным примером является кассета (последовательный — нужно быстро перемотать более ранние песни, чтобы добраться до более поздних) и компакт- диск (прямой доступ — можно перейти к нужному треку, зная, что он будет извлечен).
В структурах данных прямой доступ подразумевает возможность доступа к любой записи в списке за постоянное время (независимо от ее положения в списке и размера списка). Очень немногие структуры данных могут гарантировать это, кроме массивов (и связанных структур, таких как динамические массивы ). Прямой доступ требуется или, по крайней мере, ценен во многих алгоритмах, таких как бинарный поиск , целочисленная сортировка или определенные версии решета Эратосфена . [4]
Другие структуры данных, такие как связанные списки , жертвуют прямым доступом, чтобы разрешить эффективные вставки, удаления или переупорядочивание данных. Самобалансирующиеся бинарные деревья поиска могут обеспечить приемлемый компромисс, где время доступа не одинаково для всех членов коллекции, но максимальное время для извлечения данного члена растет только логарифмически с его размером.