IndexedSeq.last 复杂度

Question

在使用索引集合时（最常见的是 immutable Vectors），我经常使用 coll.last 作为 coll(coll.size-1) 的便捷快捷方式。当随机检查我的来源时，我点击查看 last 实现，IntelliJ IDE 将我带到 TraversableLike.last 实现，它遍历所有元素最终到达最后一个。

这让我很吃惊，现在我不确定这是什么原因。 last真的是这么实现的吗？是否有某些原因阻止 last 有效地实现 IndexedSeq（或者可能 IndexedSeqLike）？

(使用的Scala SDK是2.11.4)

Answer 1

IndexedSeq 不会覆盖 last（它仅从 TraversableLike 继承它）——特定序列支持索引访问的事实并不一定使索引查找比遍历更快。然而，这样的优化实现are given in IndexedSeqOptimized, which I would expect many implementations to inherit from. In the specific case of Vector, last is overridden explicitly in the class itself.

Answer 2

IndexedSeq 对任意元素具有恒定的访问时间。 LinearSeq 具有线性时间。 TraversableLike 只是通用接口，您可能会发现它在 IndexedSeqOptimized trait:

中被覆盖了

A template trait for indexed sequences of type IndexedSeq[A] which optimizes the implementation of several methods under the assumption of fast random access.

def last: A = if (length > 0) this(length - 1) else super.last

您可能还会在 Vector.getElem 中找到快速随机访问实现 - 它使用具有高分支因子的数组树，因此通常它的 O(1) apply。它不使用 IndexedSeqOptimized，但它有自己的覆盖 last:

override /*TraversableLike*/ def last: A = {
    if (isEmpty) throw new UnsupportedOperationException("empty.last")
    apply(length-1)
}

所以它在 Scala 集合中有点混乱，这对于 Scala 内部来说很常见。不管怎样，IndexedSeqs 上的 last 实际上是 O(1) ，不管这种棘手的集合架构如何。

Scala 集合的复杂性实际上是一个活跃的话题。可以在 Paul Phillips: Scala Collections: Why Not?, and Paul Phillips is developing his alternate version of std.

找到有关 Scala 的集合框架批评的谈话（和幻灯片）

IndexedSeq.last 复杂度

IndexedSeq.last complexity

collections

performance

scala

vector