Scala的ListBuffer的大小運行時間是多少？

它是恆定的還是O（n）？如果O（n）存在具有恆定時間大小操作的類似數據結構？Scala的ListBuffer的大小運行時間是多少？

2011-08-15 deltanovember

奇怪的是，size和length在ListBuffer docs中有不同的描述。當然，ListBuffer.length是恆定的時間。在Scala 2.8之前，length確實是O（n），但是這是now fixed。在TraversableOnce中的implementation of size表明它是O（n），但我可能會遺漏一些東西。

斯卡拉收藏的其他性能特點是documented here。對於ListBuffer具體而言，

   head  tail  apply update prepend append insert 
ListBuffer C  L  L  L  C  C  L

其中C是常數而L是線性時間。

編輯： - ：https://issues.scala-lang.org/browse/SI-4933

來源

2011-08-15 05:10:40

兩個'length'和'size'上'TraversableOnce線性兩者ListBuffer長度和尺寸現在O（1）由@KiptonBarros提到的問題用的Scala 2.9.1看到關閉'。實際上，'ListBuffer'上的'size'是線性的，因爲它被轉發到'List'，它是'ListBuffer'上的'List'。這值得一票。 –

有趣的是'append'是不變的，'tail'保持線性。 –

'tail'生成一個新的集合，'append'突變現有的集合。 – soc

Scala的ListBuffer的大小運行時間是多少？

回答

相關問題