在 Scala 标准库中的 ArrayBuffer 实现中可能效率低下

Question

在学习编程时，我想我偶然发现了Scala的低效率，因为我们材料中的描述是正确的。我的一位朋友证实了更轻松的实施的可能性，他在国际信息学奥林匹克竞赛中获得了银牌和铜牌。

在我们的学习材料中，它写道："例如，对于 ArrayBuffer，在末尾附加元素非常有效：由于内部数组的大小总是翻倍，因此很少分配和复制到新数组。相比之下，在开头预置元素非常耗时，因为每次调用该方法时都会分配一个新的内部数组，并将元素复制到该数组中。

难道不能有另一个数组存储索引，以便它总是将元素添加到末尾吗？

Answer 1

可能有第二个数组包含索引，但由于多种原因，效率会降低：

1. 索引数组需要额外的存储

2. 访问元素至少需要两次内存读取，而不是一次

3. 如果索引未保持排序，则每次访问都需要搜索索引数组

4. 如果索引保持排序，那么您在这个数组中会遇到与原始数组完全相同的问题。