Scala方法的渐近行为

发布时间：2020-12-16 18:54:21 所属栏目：安全来源：网络整理

导读：有什么地方我可以找到HashSet,TreeSet,List等集合上的操作的预期时间和空间复杂性？是否只是希望从抽象数据类型本身的属性中了解这些？我知道Performance characteristics for Scala collections,但这只提到了一些非常基本的操作.也许这些集合的其余操作纯

有什么地方我可以找到HashSet,TreeSet,List等集合上的操作的预期时间和空间复杂性？

是否只是希望从抽象数据类型本身的属性中了解这些？

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

解决方法

其他方法的性能特征确实难以断言.考虑以下：

>这些方法都是基于foreach或迭代器实现的,并且通常在层次结构中处于非常高的水平. Vector的地图是在collection.TraversableLike上实现的.
为了增加对伤害的侮辱,使用哪种方法实现取决于类继承的线性化.这也适用于任何称为帮助程序的方法.之前发生过这种变化导致无法预料的性能问题.
由于foreach和迭代器都是O(n),因此任何改进的性能都取决于其他方法的特化,例如大小和切片.
>对于其中许多人而言,进一步依赖于提供的构建器的性能特征,这取决于调用站点而不是定义站点.

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

充其量,任何此类文档都将根据其他方法进行描述.这并不意味着它不值得,但它并不容易完成 – 开源项目的艰巨任务取决于志愿者,他们通常以他们喜欢的方式工作,而不是需要什么.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!