scala - Scala方法的渐近行为

Question

我可以在某个地方找到对HashSet，TreeSet，List等集合的预期时间和空间操作的复杂性吗？

难道人们只是希望从abstract-data-types本身的属性中了解这些吗？

我知道Performance characteristics for Scala collections，但这仅提及一些非常基本的操作。也许这些集合的其余操作完全是基于一个小的基础集构建的，但是然后，似乎只是希望我知道它们已经以这种方式实现了？

Answer 1

其他方法的性能特征确实很难断言。考虑以下:

这些方法都是基于foreach或iterator来实现的，并且在层次结构中通常处于很高的级别。 Vector的map是在collection.TraversableLike上实现的。
为了增加侮辱性，使用哪种方法实现取决于类继承的线性化。这也适用于任何称为辅助方法的方法。在此之前的更改导致无法预料的性能问题之前就已经发生过。
由于foreach和iterator都是O(n)，因此任何性能的改善都取决于其他方法的特化，例如size和slice。

对于它们中的许多而言，它们进一步依赖于所提供的构建器的性能特征，该构建器的性能特征取决于调用站点而不是定义站点。

因此结果是，定义和记录该方法的地方没有足够的信息来陈述其性能特征，并且可能不仅取决于继承集合如何实现其他方法，甚至取决于从CanBuildFrom获得的对象Builder的性能特征，该特性在调用站点传递。

充其量，任何此类文档都将以其他方法进行描述。这并不意味着不值得，但并不容易完成-开源项目上的艰巨任务取决于志愿者，他们通常按自己喜欢的方式工作，而不是所需的工作。