Прямой доступ к данным: что это такое? Объяснение принципа произвольного доступа к элементам последовательности в компьютерных науках. Сравнение с последовательным доступом.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Случайный доступ (более точно и в более широком смысле называемый прямым доступом) — это возможность доступа к произвольному элементу последовательности за одинаковое время или к любому элементу данных из совокупности адресуемых элементов примерно так же легко и эффективно, как и к любому другому, независимо от количества элементов в наборе. В информатике это обычно противопоставляется последовательному доступу, который требует извлечения данных в том порядке, в котором они были сохранены. Например, данные могут быть логически организованы в виде одной последовательности, такой как строка, в двух измерениях, как строки и столбцы на поверхности, или в нескольких измерениях. Однако, имея все координаты, программа может получить доступ к каждой записи примерно так же быстро и легко, как и к любой другой. В этом смысле выбор элемента данных является произвольным, поскольку для его поиска требуется только его адрес, то есть координаты его местоположения, такие как номер строки и столбца (или номер дорожки и записи на магнитном барабане). Изначально термин «случайный доступ» использовался, поскольку процесс должен был находить записи независимо от порядка их запроса. Однако вскоре термин «прямой доступ» стал более распространенным, поскольку позволял непосредственно извлекать запись, независимо от ее позиции. Ключевой характеристикой, однако, является то, что устройство может немедленно получить доступ к любой необходимой записи по запросу. Обратным является последовательный доступ, при котором для доступа к удаленному элементу требуется больше времени. Типичным примером этого различия является сравнение древнего свитка (последовательный; весь материал перед нужными данными должен быть развернут) и книги (прямой: можно сразу открыть любую произвольную страницу). Более современным примером является кассетная лента (последовательный — необходимо перемотать вперед через предыдущие песни, чтобы добраться до последующих) и компакт-диск (прямой доступ — можно перейти к нужному треку, зная, что он будет извлечен). В структурах данных прямой доступ подразумевает возможность доступа к любой записи в списке за постоянное время (независимо от ее позиции в списке и размера списка). Очень немногие структуры данных могут гарантировать это, за исключением массивов (и связанных структур, таких как динамические массивы). Прямой доступ требуется или, по крайней мере, полезен во многих алгоритмах, таких как двоичный поиск, сортировка целых чисел или определенные версии решета Эратосфена. Другие структуры данных, такие как связные списки, жертвуют прямым доступом, чтобы обеспечить эффективное добавление, удаление или переупорядочивание данных. Самобалансирующиеся двоичные деревья поиска могут обеспечить приемлемый компромисс, когда время доступа не одинаково для всех элементов коллекции, но максимальное время извлечения данного элемента растет только логарифмически с ее размером.
Random access (more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elements may be in the set. In computer science it is typically contrasted to sequential access which requires data to be retrieved in the order it was stored. For example, data might be stored notionally in a single sequence like a row, in two dimensions like rows and columns on a surface, or in multiple dimensions. However, given all the coordinates, a program can access each record about as quickly and easily as any other. In this sense, the choice of datum is arbitrary in the sense that no matter which item is sought, all that is needed to find it is its address, i. e. the coordinates at which it is located, such as its row and column (or its track and record number on a magnetic drum). At first, the term "random access" was used because the process had to be capable of finding records no matter in which sequence they were required. However, soon the term "direct access" gained favour because one could directly retrieve a record, no matter what its position might be. The operative attribute, however, is that the device can access any required record immediately on demand. The opposite is sequential access, where a remote element takes longer time to access. A typical illustration of this distinction is to compare an ancient scroll (sequential; all material prior to the data needed must be unrolled) and the book (direct: can be immediately flipped open to any arbitrary page). A more modern example is a cassette tape (sequential — one must fast forward through earlier songs to get to later ones) and a CD (direct access — one can skip to the track wanted, knowing that it would be the one retrieved). In data structures, direct access implies the ability to access any entry in a list in constant time (independent of its position in the list and of the list's size). Very few data structures can make this guarantee other than arrays (and related structures like dynamic arrays). Direct access is required, or at least valuable, in many algorithms such as binary search, integer sorting, or certain versions of sieve of Eratosthenes. Other data structures, such as linked lists, sacrifice direct access to permit efficient inserts, deletes, or re ordering of data. Self balancing binary search trees may provide an acceptable compromise, where access time is not equal for all members of a collection, but the maximum time to retrieve a given member grows only logarithmically with its size.