Исходя из фона Java, мне интересно, почему List в Scala не имеет поля size, такого как его эквивалент Java LinkedList. В конце концов, с полем размера вы сможете определить размер списка в постоянное время, поэтому почему поле размера упало?
(Этот вопрос относится к новым классам коллекции в Scala 2.8 и более поздних версиях. Кроме того, я имею в виду неизменяемый List, а не изменяемый.)
Нельзя сказать, что поле размера было отброшено, так как такой список без размера существует в течение 50 лет с LISP, где они повсеместны, и они очень распространены в ML и Haskell тоже, влиятельные в scala.
Основная причина заключается в том, что список является рекурсивной структурой. Не пустым List является Cons(head: A, tail: List[A]) - за исключением того, что Cons на самом деле называется ::, чтобы обеспечить удобную инфиксную нотацию. Вы можете получить доступ к хвосту (список без элемента head), и это тоже список. И это делается почти все время. Таким образом, наличие счетчика в списке не означает добавление только одного целого числа, но столько целых чисел, сколько есть элементов. Это возможно, но, конечно, не бесплатно.
Если вы сравниваете с java LinkedList, LinkedList имеет рекурсивную реализацию (основанную на Node, которая более или менее похожа на Cons, но со ссылками в обоих направлениях). Но LinkedList не является Node, он им владеет (и сохраняет их количество). Таким образом, хотя он имеет рекурсивную реализацию, вы не можете обрабатывать его рекурсивно. Вы хотели бы, чтобы хвост LinkedList как LinkedList, вам придется либо удалить голову, либо изменить свой список, либо скопировать все элементы хвоста в новый LinkedList. Поэтому scala List и java LinkedList - очень разные структуры.
Поскольку сохранение этого поля будет
В Java обычно создается LinkedList, а затем обрабатывается без создания новых списков путем добавления/удаления элементов; в Scala создано много List.
Итак, было решено, что накладные расходы не стоят того.
Список определяет размер:
> List(1, 2, 3).size
res4: Int = 3
который имеет линейное o (n) время выполнения. Если вам действительно нужно постоянное время, вы должны рассмотреть изменяемый ListBuffer, который обеспечивает постоянную реализацию размера времени.
"Недостаток" сложности O (n) не такой большой, как вы думаете. Мартин Одерски упоминал в разговоре, что (если я правильно помню) 90% всех списков, созданных во всех программах на любом компьютерном языке, имеют размер 4 или меньше. (Это было в контексте неизменности и эффективности)
Следовательно, время доступа O (n) для size не является таким большим накладным расходами для большинства созданных списков, и, как другие, упомянутые здесь, экономия памяти более чем компенсирует это.
Вы проверили поле length?
Мне что-то не хватает? Размер:
Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_29).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import scala.collection.immutable.List
import scala.collection.immutable.List
scala> val a = List(1,2,3)
a: List[Int] = List(1, 2, 3)
scala> a size
res0: Int = 3