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です。 implementation of sizeがTraversableOnceであることは、それがO（n）であることを示唆していますが、何か不足している可能性があります。

その他のScalaコレクションのパフォーマンス特性はdocumented hereです。 ListBufferのために特別に、

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

Cは定数であり、Lは線形時間です。

編集：ListBuffer長さとサイズの両方について、（1）Oれる - @KiptonBarros言及問題はスカラで閉じた参照2.9.1：https://issues.scala-lang.org/browse/SI-4933

出典

2011-08-15 05:10:40

両方 'length'と' size'はTraversableOnce 'に線形であります'。実際、 'ListBuffer'の' size'は 'underlying'に転送されるため、' ListBuffer'の 'size'は線形です。これは' ListBuffer'の 'List'です。それはチケットの価値がある。 –

'append'は定数で、' tail'は線形のままです。 –

'tail 'は新しいコレクションを生成し、' append'は既存コレクションを変更します。 – soc

ScalaのListBufferでの実行時間はどのくらいですか？

答えて

関連する問題