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