MGw*_*nne 6 scala time-complexity
有什么地方我可以找到HashSet,TreeSet,List等集合上的操作的预期时间和空间复杂性？
是否只是希望从抽象数据类型本身的属性中了解这些？
我知道Scala集合的性能特征,但这只提到了一些非常基本的操作.也许这些集合的其余操作纯粹是从一个小的基础集构建的,但是,似乎我只是希望知道他们已经以这种方式实现了它们？
其他方法的指南应该是 - 只考虑一个有效的实现应该是什么样子.
集合上的大多数其他批量操作(处理集合中每个元素的操作)都是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)在大多数情况下.
其他方法的性能特征确实很难断言。考虑以下：
foreach或实现的iterator，并且通常在层次结构中非常高的级别上实现。例如，Vector是map在 上实现的。collection.TraversableLike雪上加霜的是，使用哪种方法实现取决于类继承的线性化。这也适用于任何称为助手的方法。以前曾发生过此处的更改导致不可预见的性能问题的情况。由于foreach和iterator都是O(n)，任何改进的性能都取决于其他方法的专业化，例如size和slice。因此，结果是定义该方法并记录该方法的地方没有足够的信息来说明其性能特征，并且可能不仅取决于继承集合如何实现其他方法，甚至还取决于继承集合如何实现其他方法。从 CanBuildFrom 获得的对象 Builder 的性能特征，该对象在调用站点传递。
最好的情况是，任何此类文档都可以用其他方法来描述。这并不意味着它不值得，但它并不容易完成——开源项目的艰巨任务取决于志愿者，他们通常做自己喜欢的事情，而不是需要做的事情。