Random access and Sequential acc

image.png

Random access

Random access---wikipedia
在计算机科学中，随机访问（更准确并且更普遍的叫法是直接访问）是从大量的可寻址元素的数据中访问任何元素大致和访问其他元素一样简洁有效，不管多少元素在这个集合中。与随机访问相反的是顺序访问

例如，数据理论上可以以一维结构储存，例如行，以二维结构储存，例如一个平面的行和列（坐标系），或者更多维度。无论如何，给定坐标，一个程序可以快速有效的访问任意坐标点，在这个层面上来说，数据项的选择是任意的，无论要寻找哪个数据项，找到它都需要它的地址，也就是说，它所位于的坐标。一开始是用术语"random access"，因为process不管在哪个序列都能根据需求找到记录，然而很快，大家觉得术语"direct access"更贴切，因为不管记录在哪，都能直接检索。但是不管术语是怎么叫，操作属性都是，设备能根据需求立即访问任何记录。相对的是顺序访问，表示更远的元素需要更长的时间去访问

直接访问和顺序访问差别的直观的例子是，古代的卷轴和图书，要看卷轴的内容需要一点一点展开，就像顺序访问一样，而图书就像直接访问，直接翻到想看的那一页就可以。一个更现代的例子是磁带和CD，在磁带中要听后面的歌需要跳过前面的歌，但是在CD中可以任意听任一首歌

在数据结构中，直接访问意味着访问列表的任意一项的时间是固定的（不管在列表的位置和列表的规模）。但是很少的数据结构能保证这一点，除了数组（和相关的结构例如动态数组）。在许多数据结构中，直接访问是必需而且有意义的，例如binary search, integer sorting或者某些版本的sieve of Eratosthense。

其他的数据结构，例如链表，牺牲直接访问来保证有效的插入，删除或者记录数据。Self-balancing binary search tree提供了可接受的折中，对于集合中所有成员的访问时间是不相等的，但是检索给定成员的最大时间仅以其大小的对数增长

Sequential access

Sequential access---wikipedia
在计算机科学中，顺序访问意味着一组元素（例如内存数组中的数据，或磁盘文件，或磁带数据存储器）以预定的，有序的序列被访问，顺序访问有时是访问数据的唯一方式，例如访问磁带的数据。它有时也是可选的访问方法，例如，如果想要有序的处理一序列数据元素

然后，顺序访问或顺序性没有一致的定义，事实上，不同的顺序性定义会导致不同的顺序性量化结果。在空间维度上，请求大小，跨越距离，方向访问，重复访问都可能影响顺序性。对于时间顺序性，诸如多流和到达间隔的时间阈值等特征对顺序性的定义有影响

在数据结构中，如果访问某个值必需以特定的顺序，那么数据结构就是顺序访问。典型的例子就是链表，索引到具有顺序访问的列表需要O(n)的时间复杂度，其中n为索引。结果，许多算法例如quicksort和binary search退化成低效的算法，甚至比原来的算法效率更低，这些算法如果不使用随机访问是不实际的。在另一方面，某些算法，通常是没有索引的算法，恰恰需要顺序访问，例如mergesort，而没有副作用