Scala: Помогите мне понять производительность Список

Question

List Scaladoc говорит:

Время: Список имеет O (1) перед именем и голова/хвост доступа.

val mainList = List(3, 2, 1) 
val with4 = 4 :: mainList // re-uses mainList, costs one :: instance 
val with42 = 42 :: mainList // also re-uses mainList, cost one :: instance 
val shorter = mainList.tail // costs nothing as it uses the same 2::1::Nil instances as mainList 

Что значит "стоит один экземпляр ::"? (Ссылка на O(1) заключается в предоставлении контекста, это не то, о чем я прошу. Мой вопрос касается высказываний комментариев).

Answer 1

думаю есть costs one :: instance потребление памяти предназначено. Когда вы сделаете 4 :: mainList, scala создаст новый экземпляр ::. Когда вы делаете mainList.tail, scala не нужно ничего создавать.

Это очень важно, чтобы показать, потому что для всего блока

val mainList = List(3, 2, 1) 
val with4 = 4 :: mainList // re-uses mainList, costs one :: instance 
val with42 = 42 :: mainList 

Scala выдает только 5 :: экземпляров, вместо 8.

Это, безусловно, не о производительности, потому что вы не можете скажем, что mainList.tail ничего не стоит с точки зрения производительности.