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

Random access
Произвольный доступ по сравнению с последовательный доступ

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

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

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

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

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

Рекомендации

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

Смотрите также