Scala的ListBuffer上的大小运行时间是多少？
发布时间：2020-12-16 08:47:42 所属栏目：安全 来源：网络整理
导读：它是常数还是O(n)？如果O(n)存在具有恒定时间大小操作的类似数据结构？ 解决方法 奇怪的是,大小和长度在 ListBuffer docs中有不同的描述.当然,ListBuffer.length是常量时间.在Scala 2.8之前,长度确实是O(n),但这是 now fixed.TraversableOnce中的 implementa
|
它是常数还是O(n)？如果O(n)存在具有恒定时间大小操作的类似数据结构？
解决方法
奇怪的是,大小和长度在
ListBuffer docs中有不同的描述.当然,ListBuffer.length是常量时间.在Scala 2.8之前,长度确实是O(n),但这是
now fixed.TraversableOnce中的
implementation of
size表明它是O(n),但我可能会遗漏一些东西.
Scala集合的其他性能特征是documented here.具体来说,对于ListBuffer, head tail apply update prepend append insert ListBuffer C L L L C C L 其中C是常数,L是线性时间. 编辑：ListBuffer的长度和大小现在都是O(1) – @KiptonBarros提到的问题是用Scala 2.9.1关闭的,请参阅：https://issues.scala-lang.org/browse/SI-4933 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |