Произвольный доступ

Произвольный доступ (точнее и чаще называемый прямым доступом ) — это возможность получить доступ к произвольному элементу последовательности за равное время или к любому элементу данных из совокупности адресуемых элементов примерно так же легко и эффективно, как и к любому другому, независимо от того, сколько элементов может быть доступно. быть в наборе. В информатике его обычно противопоставляют последовательному доступу , который требует извлечения данных в том порядке, в котором они были сохранены.

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

Типичной иллюстрацией этого различия является сравнение древнего свитка (последовательный; весь материал, предшествующий необходимым данным, должен быть развернут) и книги (прямой: его можно немедленно открыть на любой произвольной странице ). Более современный пример — кассета (последовательная — нужно перемотать более ранние песни вперед, чтобы перейти к более поздним) и компакт -диск (прямой доступ — можно перейти к нужной дорожке, зная, что она будет найдена).

В структурах данных прямой доступ подразумевает возможность доступа к любой записи списка за постоянное время (независимо от ее положения в списке и размера списка). Очень немногие структуры данных могут обеспечить такую гарантию, кроме массивов (и связанных с ними структур, таких как динамические массивы ). Прямой доступ необходим или, по крайней мере, ценен во многих алгоритмах, таких как двоичный поиск , целочисленная сортировка или некоторые версии решета Эратосфена . ^[4]

Другие структуры данных, такие как связанные списки , жертвуют прямым доступом ради эффективной вставки, удаления или изменения порядка данных. Самобалансирующиеся двоичные деревья поиска могут обеспечить приемлемый компромисс, когда время доступа не одинаково для всех членов коллекции, но максимальное время для извлечения данного элемента увеличивается только логарифмически с его размером.

Ссылки

^ Национальная компьютерная конференция и выставка (1957). Слушания . Проверено 2 октября 2013 г.
^ Введение в устройства хранения данных IBM с прямым доступом и методы организации . Международная корпорация бизнес-машин. 1966. С. 3– . Проверено 2 октября 2013 г.
^ «Случайный и последовательный доступ к данным» .
^ ДЕ КНУТ (1969). Искусство компьютерного программирования. Том. 3. Сортировка и поиск . Аддисон-Уэсли. ISBN 978-0-201-03803-3 . Проверено 2 октября 2013 г.

См. также

Поток данных
Машина произвольного доступа
Память с произвольным доступом, хотя кеш и виртуальная память делают это уже не по-настоящему произвольным доступом.
Местоположение ссылки

[Exposition1957-1] Национальная компьютерная конференция и выставка (1957). Слушания . Проверено 2 октября 2013 г.

[Division1966-2] Введение в устройства хранения данных IBM с прямым доступом и методы организации . Международная корпорация бизнес-машин. 1966. С. 3– . Проверено 2 октября 2013 г.

[3] «Случайный и последовательный доступ к данным» .

[KNUTH1969-4] ДЕ КНУТ (1969). Искусство компьютерного программирования. Том. 3. Сортировка и поиск . Аддисон-Уэсли. ISBN 978-0-201-03803-3 . Проверено 2 октября 2013 г.

[1]

[2]

[3]

[4]