斯卡拉方法的渐近行为

Question

是否有某处我可以找到预期的时间和空间像HashSet，TreeSet，List等集合上的操作的复杂性？

是否有人希望从抽象数据类型本身的属性中知道这些？

我知道Performance characteristics for Scala collections，但这只提到一些非常基本的操作。也许这些集合的其余操作纯粹是从一个小的基础集合中构建的，但是，那么我只是希望知道他们已经以这种方式实现了它们？

Answer 1

其他方法的性能特征很难断言。考虑以下几点：

• 这些方法都是基于foreach或iterator全部实现，并且通常在非常高的水平的层次结构。例如，Vector的map在collection.TraversableLike上实现。 若要添加侮辱伤害，使用哪种方法实现取决于类继承的线性化。这也适用于任何称为助手的方法。之前发生的变化造成了无法预料的性能问题。 由于foreach和iterator都是O(n)，任何改进的性能取决于其他方法的专业化，如size和slice。
• 对于其中许多人来说，进一步依赖于所提供的构建器的性能特征，这取决于调用站点而不是定义站点。

所以结果是，方法被定义并记录在案的地方没有足够的信息来陈述其性能特征，并且可能不仅取决于继承如何实现其他方法集合，但是即使是通过从CanBuildFrom获取的对象Builder的构建器的性能特征，也可以通过调用站点传递。

充其量，任何这样的文档都会用其他方法来描述。这并不意味着它是不值得的，但这并不容易 - 开源项目上的艰巨任务取决于志愿者，他们通常以他们喜欢的方式工作，而不是需要什么。

Answer 2

其他方法的指南应该是 - 只要想一下有效的实现应该是什么样子。

集合上的大多数其他批量操作（处理集合中每个元素的操作）为O(n)，因此它们在此处未提及。例子是filter，map，foreach，indexOf，reverse，find ...

方法返回的迭代器或流像combinations和permutations通常O(1)。

涉及2个藏品的方法通常是O(max(n, m))或O(min(n, m))。这些都是zip，zipAll，sameElements，corresponds，...

方法union，diff，并intersect是O(n + m)。

排序变体自然是O(nlogn)。在当前实现中，groupBy是O(nlogn)。 indexOfSlice使用KMP算法并且是O(m + n)，其中m和n是字符串的长度。

方法如+:，:+或patch通常O(n)，除非你正在处理的不可变集合为所讨论的操作是更有效的特定情况下 - 例如，在官能List前面加上一个元件或将元素附加到Vector。

方法toX通常是O(n)，因为他们必须遍历所有元素并创建一个新的集合。 toStream是一个例外，它懒洋洋地构建了这个集合 - 因此它是O(1)。此外，无论何时X是集合的类型toX只是返回this，是O(1)。

迭代器实现应该有一个O(1)（摊销）next和hasNext操作。迭代器创建应该是最差情况O(logn)，但在大多数情况下是O(1)。