为什么在Scala中索引序列比线性索引更快？
Scala中有两种类型的序列(它可以变得更通用；而不是Scala特有的)。
1. Linear Sequence, where random access of elements involves traversal from one end to the element which is a slower process.
2. Indexed Sequence, where random access of elements is really quick.我想知道为什么访问索引序列中的元素会更快？
是因为在它们的底层实现中使用了指针吗？(地址的计算公式为:基地址+(元素大小*要检索的元素的索引))
如果这是真的，为什么线性序列不能以同样的方式实现呢？而且本可以做得更快。
回答 2
Stack Overflow用户
发布于 2020-05-04 13:42:21
来自ScalaDocs page：“向量是由宽度为32的基数平衡的指状树实现的。”正如您所描述的，Array是通过地址算法进行索引的。两者都提供非常快速的随机访问(读取“索引”)检索。
另一方面，List为每个索引访问执行缓慢的线性查找。那么为什么列表在Scala代码中如此流行呢？
这是因为随机访问并不是访问集合元素的唯一方式。例如，如果您想简单地遍历序列，那么List是非常有效的。
我在某处读到Martin Odersky曾经做过一个实验，他用Vector替换了编译器代码中的每个List。结果是编译器变慢了。
Stack Overflow用户
发布于 2020-05-04 16:00:37
如果这是真的，为什么线性序列不能以同样的方式实现呢？而且本可以做得更快。
因为这样它就不再是一个线性序列了，它将是一个随机访问的索引序列。
在内存需求方面有一些重要的区别:一个数组需要一个单一的、扁平的、连续的内存块。例如，如果你想在一个数组中存储40亿个SHA-1散列，你需要一个巨大的、单一的、扁平的、连续的、未使用的128个Gioctet块。而使用单链表，您将需要40个八位字节的40亿个小块。这很容易找到，尽管它总共使用了更多的内存(160个Gioctet而不是128个Gioctet，即增加了25% )，因为你必须保留next指针。
https://stackoverflow.com/questions/61585468
复制相似问题
腾讯云开发者
