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