Почему в Scala List нет поля размера?

Question

Исходя из фона Java, мне интересно, почему List в Scala не имеет поля size, как его эквивалент Java LinkedList. В конце концов, с помощью поля размера вы сможете определять размер списка в постоянном времени, так почему же поле размера было пропущено?

(Этот вопрос относится к новым классам коллекций в Scala 2.8 и более поздних версиях. Также я имею в виду неизменяемый List, а не изменяемый.)

Answer 1

Нельзя сказать, что поле размера было отброшено , так как такой список без размера существовал в течение 50 лет после LISP, где они вездесущи, и они очень распространены в ML и Haskell, оба влияют на scala,

Основная причина в том, что список является рекурсивной структурой.Непустое значение List равно Cons(head: A, tail: List[A]) - за исключением того, что Cons фактически называется ::, чтобы обеспечить удобную инфиксную запись.Вы можете получить доступ к хвосту (список без элемента head), и это тоже список.И это делается почти все время.Таким образом, наличие счетчика в списке означало бы не добавление только одного целого числа, а столько целых чисел, сколько есть элементов.Это возможно, но, конечно, не бесплатно.

Если сравнить с LinkedList в java, LinkedList имеет рекурсивную реализацию (основанную на Node, которая более или менее похожа на Cons, но со ссылками в обоих направлениях).Но LinkedList не является узлом, он владеет ими (и ведет их учет).Таким образом, пока он имеет рекурсивную реализацию, вы не можете обращаться с ним рекурсивно.Если вы хотите использовать хвост LinkedList в качестве LinkedList, вам придется либо удалить заголовок и изменить свой список, либо скопировать все элементы tail в новый LinkedList.Так что List в Scala и LinkedList в Java - это очень разные структуры.

Answer 2

Поскольку поддержание этого поля будет

1. Добавление дополнительной памяти во все списки;
2. Добавление незначительных временных затрат при каждом создании списка.

В Javaобычно создается LinkedList, а затем манипулируется без создания новых списков путем добавления / удаления элементов;в Scala создано множество List.

Поэтому было решено, что накладные расходы не стоят этого.

Answer 3

«Недостаток» сложности O (n) не так велик, как вы могли подумать. Мартин Одерский упомянул в своем выступлении, что (если я правильно помню) 90% всех списков, созданных во всех программах на любом языке компьютера, имеют размер 4 или меньше. (Это было в контексте неизменности и эффективности)

Следовательно, время доступа O (n) для size не так уж и много для большинства созданных списков, и, как уже упоминалось здесь, экономия памяти более чем компенсирует это.

Answer 4

Список определяет размер:

> List(1, 2, 3).size
res4: Int = 3

с линейным временем выполнения o (n). Если вам действительно нужно постоянное время, вы должны рассмотреть изменяемый ListBuffer, который обеспечивает реализацию с постоянным размером времени.

Answer 5

Вы проверили поле длина ?

Answer 6

я что-то упустил? Размер есть:

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