Каково время выполнения для размера в ListBuffer Scala?

Question

Это константа или O (n)?Если O (n), существуют ли подобные структуры данных с операциями с постоянным размером времени?

Answer 1

Как ни странно, size и length имеют разные описания в документации ListBuffer .Конечно, ListBuffer.length - это постоянное время.До Scala 2.8 length действительно было O (n), но теперь исправлено .Реализация size в TraversableOnce предполагает, что это O (n), но я могу что-то упустить.

Другие характеристики производительности коллекций Scala задокументированы здесь.Для 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