Mutable.ListBuffer в Scala, похоже, использует функцию хвоста List, но задокументировано, что она имеет линейную сложность?

Question

Начиная с версии 2.12.8 текущей документации , хвост List постоянен, а хвост ListBuffer линейен.Однако, глядя на исходный код , похоже, что для функции tail нет перезаписи, и в большинстве случаев использования (например, удаление элемента head) явно вызывается функция хвоста List.Поскольку ListBuffer, кажется, немного больше, чем обертка List с длиной var и указателем на последний элемент, почему он линейный?

Я рассчитал оба метода, и на самом деле кажется, что хвост List постоянен, а хвост ListBufferдействительно линейно:

import scala.collection.mutable
import scala.collection.immutable

val immutableList: immutable.List[Int] = (1 to 10000).toList
val mutableListBuffer: mutable.ListBuffer[Int] = mutable.ListBuffer.empty[Int] ++= (1 to 10000).toList

// Warm-up
(1 to 100000).foreach(_ => immutableList.tail)
(1 to 100000).foreach(_ => mutableListBuffer.tail)

// Measure
val start = System.nanoTime()
(1 to 1000).foreach(_ => immutableList.tail)
val middle = System.nanoTime()
(1 to 1000).foreach(_ => mutableListBuffer.tail)
val stop = System.nanoTime()

println((middle - start) / 1000)
println((stop - middle) / 1000)

Результаты были, как задокументировано:

1076
86010

Однако, если вы используете такие функции, как remove (0), которые используют хвост List, он будет постоянным сследующие результаты:

1350
1724

Я ожидаю, что сложность линейности возникает из-за построения целого нового списка для возврата, но, поскольку внутренняя структура является списком, почему бы не вернуть хвост списка?

Answer 1

, поскольку внутренняя структура представляет собой список

Если вы посмотрите на источник , внутренняя структура на самом деле представляет собой два списка:

private var start: List[A] = Nil
private var last0: ::[A] = _

last0 имеет этот тип, потому что он мутирует, используя внутренний API (и это должно быть для ListBuffer, чтобы иметь смысл) (на самом деле, просто наличие двух списков для передней и задней частей со спинойчасть в обратном порядке должна достаточно эффективно поддерживать все операции ListBuffer, включая (амортизированную) O (1) tail; предположительно текущая реализация выигрывает от постоянных факторов, или, может быть, мне не хватает какой-то операции, которая работает намного лучше).

Так что tail не может просто "вернуть хвост списка": ему по крайней мере придется копировать last0, потому что вы не можете разделить одну и ту же изменяемую часть между двумя буферами.Даже если бы дизайнеры хотели, чтобы изменения в tail отражали изменения в исходном ListBuffer и наоборот, совместное использование last0 не имело бы такого эффекта (без особых усилий).Это уже линейно.

Обратите внимание, что если тип возврата ListBuffer#tail был List, вам также необходимо скопировать last0 или скопировать содержимое из last0 в start перед возвратом хвоста и т. Д.не делать tail постоянное время.Но это создает дополнительные проблемы: ArrayBuffer#tail возвращает Array?Как вы объявляете тип возврата tail в GenTraversableLike, если он все еще доступен там?

Answer 2

ListBuffer не расширяет List, и тот факт, что он не переопределяет tail, не означает, что он использует List#tail.Если вы посмотрите на раздел Definition Classes в документации для tail на ListBuffer, вы увидите, что он исходит от TraversableLike, где он определен так:

override def tail: Repr = {
  if (isEmpty) throw new UnsupportedOperationException("empty.tail")
  drop(1)
}

И если вы посмотрите на drop, вы увидите, что он использует конструктор для создания новой коллекции, содержащей все элементы, кроме первого, что объясняет, почему он линейный.

Как подсказывает talex в комментариях выше, ListBuffer#tail должен возвращать новую коллекцию, поскольку исходный буфер может быть изменен, и разработчики стандартной библиотеки решили, что вы не хотите, чтобы эти изменения отражались в результате, полученном вами tail.