Почему в Scala List нет поля размера?
Исходя из фона Java, мне интересно, почему List в Scala не имеет поле размера , как его эквивалент в Java LinkedList . В конце концов, с помощью поля размера вы сможете определить размер списка в постоянное время, так почему же поле размера было удалено?
(Этот вопрос относится к новым классам коллекций в Scala 2.8 и более поздних версиях. Кроме того, я имею в виду неизменяемый список , а не изменяемый.)
3 ответа
Нельзя сказать, что поле размера было удалено , так как такой список без размера существовал в течение 50 лет после LISP, где они вездесущи, и они очень распространены в ML и Haskell, оба влиятельные в scala ,
Основная причина в том, что список является рекурсивной структурой. Непустым List является Cons(head: A, tail: List[A]) - за исключением того, что Cons на самом деле называется ::, чтобы обеспечить удобную инфиксную запись. Вы можете получить доступ к хвосту (список без элемента head), и это тоже список. И это делается почти все время. Таким образом, наличие счетчика в списке означало бы не добавление только одного целого числа, а столько же целых чисел, сколько есть элементов. Это возможно, но, конечно, не бесплатно.
Если вы сравните с LinkedList в java, LinkedList имеет рекурсивную реализацию (на основе Node, которая более или менее похожа на Cons, но со ссылками в обоих направлениях). Но LinkedList не является узлом, он владеет ими (и ведет их учет). Таким образом, пока он имеет рекурсивную реализацию, вы не можете обращаться с ним рекурсивно. Если вы хотите использовать хвост LinkedList в качестве LinkedList, вам придется либо удалить заголовок и изменить свой список, либо скопировать все элементы tail в новый LinkedList. Так что scala List и java LinkedList - это очень разные структуры.
Поскольку поддержание этого поля будет
- Добавлять накладные расходы памяти во все списки;
- Добавлять незначительные накладные расходы времени при каждом создании списка.
В Java обычно создается LinkedList, а затем обрабатываются без создания новых списков путем добавления / удаления элементов; в Scala создано много List.
Поэтому было решено, что накладные расходы не стоят того.