Последовательный доступ к данным: характеристики и влияние на алгоритмы.
Sequential access
Последовательный доступ к данным: что это такое? Узнайте о принципах, отличиях от произвольного доступа и областях применения в компьютерных технологиях.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Последовательный доступ — это термин, описывающий доступ к группе элементов (например, к данным в массиве памяти, на диске или магнитной ленте) в заранее установленной, упорядоченной последовательности. Он противоположен произвольному доступу, который позволяет обращаться к любому элементу последовательности так же легко и эффективно, как и к любому другому, в любой момент времени. Последовательный доступ иногда является единственным способом доступа к данным, например, при работе с данными на магнитной ленте. Он также может быть предпочтительным методом доступа, например, когда требуется последовательная обработка элементов данных.
Sequential access is a term describing a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) being accessed in a predetermined, ordered sequence. It is the opposite of random access, the ability to access an arbitrary element of a sequence as easily and efficiently as any other at any time. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape. It may also be the access method of choice, for example if all that is wanted is to process a sequence of data elements in order.
Определение
В информатике отсутствует единое определение последовательного доступа или последовательности. Более того, различные определения последовательности могут приводить к разным результатам её количественной оценки. В пространственном измерении на последовательность могут влиять размер запроса, расстояние между запросами, обращения назад и повторные обращения. Для временной последовательности на определение последовательности влияют такие характеристики, как многопоточность и пороговое значение интервала между запросами. В структурах данных структура данных считается имеющей последовательный доступ, если её элементы можно посещать только в определенном порядке. Классическим примером является связный список. Индексация в список с последовательным доступом требует O(n) времени, где n – индекс. В результате многие алгоритмы, такие как быстрая сортировка и двоичный поиск, деградируют до неэффективных алгоритмов, которые даже менее производительны, чем их наивные аналоги; эти алгоритмы непрактичны без произвольного доступа. С другой стороны, некоторые алгоритмы, как правило, те, которые не используют индексы, требуют только последовательного доступа, например, сортировка слиянием, и не испытывают никаких ограничений.
There is no consistent definition in computer science of sequential access or sequentiality. In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, stride distance, backward accesses, re accesses can affect sequentiality. For temporal sequentiality, characteristics such as multi stream and inter arrival time threshold has impact on the definition of sequentiality. In data structures, a data structure is said to have sequential access if one can only visit the values it contains in one particular order. The canonical example is the linked list. Indexing into a list that has sequential access requires O(n) time, where n is the index. As a result, many algorithms such as quicksort and binary search degenerate into bad algorithms that are even less efficient than their naive alternatives; these algorithms are impractical without random access. On the other hand, some algorithms, typically those that do not have index, require only sequential access, such as mergesort, and face no penalty.