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