Sequential access

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Fabiosusanto (talk | contribs) at 01:27, 13 March 2020 (Added content). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Definition

There is no consistent definition in computer science of sequential access or sequentiality.[1][2][3][4][5][6][7][8] In fact, different sequentiality definitions can lead to different sequentiality quantification results. In spatial dimension, request size, strided 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.[9]

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.

See also

References