Scala предлагает множество конечных реализаций неизменяемых коллекций. Они отличаются реализуемыми трейтами (мапы (map), множества(set), последовательности(seq)), они могут быть бесконечными, и различаются производительностью операций. Вот некоторые из наиболее распространенных неизменяемых типов коллекций, используемых в Scala.
Списки (Lists)
List представляет из себя конечную неизменяемую последовательность. Он обеспечивает быстрый (за постоянное время) доступ как к первому элементу, так и к остальному списку, а также быструю операцию добавления нового элемента в начало списка. Большинство оставшихся операции занимают линейное время исполнения.
Ленивые Списки (LazyLists)
LazyList похож на список, за исключением того, что его элементы вычисляются лениво. Поэтому ленивый список может быть бесконечно длинным. Обрабатываются только те элементы, которые запрашиваются. В остальном, у ленивых списков те же параметры производительности, что и обычных.
Если списки создаются с помощью оператора ::, то ленивые списки создаются схожей операцией #::. Вот простой пример ленивого списка с целыми числами 1, 2 и 3:
scala> val lazyList = 1 #:: 2 #:: 3 #:: LazyList.empty
lazyList: scala.collection.immutable.LazyList[Int] = LazyList(?)
На первом месте в этом ленивом списке - 1, а на втором - 2 и 3. Но ни один из элементов здесь не выводится, потому что список еще не вычислен! Ленивые списки задуманы обрабатываться лениво, поэтому метод toString не выводит всех элементов, не заставляя производить дополнительные вычисления.
Ниже приводится более сложный пример. Вычисления ленивого списка, содержащего последовательность Фибоначчи, которая начинается с заданных двух чисел. Последовательность Фибоначчи - это последовательность, в которой каждый элемент представляет собой сумму двух предыдущих элементов в серии.
scala> def fibFrom(a: Int, b: Int): LazyList[Int] = a #:: fibFrom(b, a + b)
fibFrom: (a: Int,b: Int)LazyList[Int]
Эта функция обманчиво проста. Первый элемент очевидно a, остальная часть - это последовательность Фибоначчи, начинающаяся с b, за которой следует a+b. Сложность состоит в том, чтобы вычислить эту последовательность, не вызывая бесконечной рекурсии. Если бы функция использовала :: вместо #::, то каждый вызов функции приводил бы к очередному вызову, вызывая тем самым бесконечную рекурсию. Но так как он использует #::, то вычисление правой части не производится до тех пор, пока она не будет запрошена.
Ниже приведены первые элементы последовательности Фибоначчи, начиная с двух едениц:
scala> val fibs = fibFrom(1, 1).take(7)
fibs: scala.collection.immutable.LazyList[Int] = LazyList(?)
scala> fibs.toList
res9: List[Int] = List(1, 1, 2, 3, 5, 8, 13)
Неизменяемые ArraySeqs
Списки очень эффективны в алгоритмах которые активно использует head. Получение, добавление и удаление к переднему (head) элементу списка занимает постоянное время, в то время как доступ или изменение остальных элементов в списке занимает линейное время.
Последовательный Массив (ArraySeq) это тип коллекции (добавленной в Scala 2.13) который решает проблему неэффективности случайного доступа к спискам.
ArraySeq позволяют получить доступ к любому элементу коллекции за постоянное время. В результате алгоритмы, использующие ArraySeq, могут быстро получать доступ к элементам в произвольных местах коллекции, из-за чего проще создавать эффективные алгоритмы.
ArraySeqs создаются и изменяются также, как и любые другие последовательности.
scala> val arr = scala.collection.immutable.ArraySeq(1, 2, 3)
arr: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3)
scala> val arr2 = arr :+ 4
arr2: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3, 4)
scala> arr2(0)
res22: Int = 1
ArraySeqs являются неизменяемыми, поэтому вы не можете изменять элементы непосредственно в коллекции. Однако операции updated, appended и prepended создают новые ArraySeqs, которые отличаются от базового ArraySeq только в одном элементе:
scala> arr.updated(2, 4)
res26: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 4)
scala> arr
res27: scala.collection.immutable.ArraySeq[Int] = ArraySeq(1, 2, 3)
Как видно из последней строки выше, вызов updated не влияет на исходный ArraySeq arr.
ArraySeqs хранят свои элементы в приватном Массиве. Таким образом достигается компактное представление и обеспечивается быстрый индексированный доступ к элементам, но обновление или добавление одного элемента занимает линейное время, так как требует создания другого массива и копирования всех элементов исходного массива.
Вектора (Vectors)
В предыдущих разделах мы увидели, что List и ArraySeq эффективные структуры данных в некоторых специфичных ситуациях, но они неэффективны в других: например, добавление элемента происходит за постоянное время для List, но линейно для ArraySeq, и наоборот, индексированный доступ является постоянным для ArraySeq, но линейным для List.
Вектор - тип коллекции, который обеспечивает хорошую производительность для всех своих операций. Вектора позволяют получить доступ к любому элементу последовательности за “практически” постоянное время. Это значит что константа больше, чем при получении переднего (head) элемента списка или при чтения элемента из ArraySeq, но, тем не менее, это константа. Избегайте использование векторов в алгоритмах базирующихся на активной работе с передними (head) элементами. Вектора могут получать доступ к элементам и изменять их в произвольных местах, что делает разработку более простой и удобной.
Вектора создаются и модифицируются так же, как и другие последовательности.
scala> val vec = scala.collection.immutable.Vector.empty
vec: scala.collection.immutable.Vector[Nothing] = Vector()
scala> val vec2 = vec :+ 1 :+ 2
vec2: scala.collection.immutable.Vector[Int] = Vector(1, 2)
scala> val vec3 = 100 +: vec2
vec3: scala.collection.immutable.Vector[Int] = Vector(100, 1, 2)
scala> vec3(0)
res1: Int = 100
Вектора представлены деревьями с высоким уровнем ветвления (уровень ветвления дерева или графа - это количество дочерних элементов у каждого узла). Каждый узел дерева содержит до 32х элементов вектора или содержит до 32х других узлов. Вектора с размером до 32х элементов могут быть представлены одним узлом. Вектора 32 * 32 = 1024 элементы могут быть представлены одним витком.
Для векторов с 215 элементами достаточно двух переходов от корня дерева до конечного элемента узла, трех переходов для векторов с 220 элементами, четырех переходов для 225 элементами и пяти переходов для 230 элементами. Таким образом, для всех векторов разумных размеров выбор элемента включает до 5 простых выборок массивов. Именно это мы подразумевали, когда писали, что доступ к элементам осуществляется с “практически постоянным временем”.
Так же как и доступ к элементу, операция обновления в векторах занимает “практически” постоянное время. Добавление элемента в середину вектора может быть выполнено через копирование узла содержащего этот элемент и каждого ссылающегося на него узла, начиная от корня дерева. Это означает, что процесс обновления элемента создает от одного до пяти узлов, каждый из которых содержит до 32 элементов или поддеревьев. Это, конечно, дороже, чем просто обновление элемента в изменяемом массиве, но все же намного дешевле, чем копирование вообще всего вектора.
Поскольку вектора обладают хорошим балансом между быстрой случайной выборкой и быстрым случайным обновлением элементов, они используются в качестве реализации неизменяемых индексированных последовательностей:
scala> collection.immutable.IndexedSeq(1, 2, 3)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)
Неизменяемые Очереди (Immutable Queues)
Очередь это последовательность с FIFO (первым пришёл — первым ушёл).
Вы добавляете элемент в очередь методом enqueue и достаете элемент из очереди используя метод dequeue. Эти операции - выполняются за постоянное время.
Вот как можно создать пустую неизменяемую очередь:
scala> val empty = scala.collection.immutable.Queue[Int]()
empty: scala.collection.immutable.Queue[Int] = Queue()
Вы можете добавить элемент в неизменяемую очередь используя enqueue:
scala> val has1 = empty.enqueue(1)
has1: scala.collection.immutable.Queue[Int] = Queue(1)
Чтобы добавить несколько элементов в очередь, испольуйте метод enqueueAll с коллекцией в качестве аргумента:
scala> val has123 = has1.enqueueAll(List(2, 3))
has123: scala.collection.immutable.Queue[Int]
= Queue(1, 2, 3)
Для удаления элемента из начала очереди используется команда dequeue:
scala> val (element, has23) = has123.dequeue
element: Int = 1
has23: scala.collection.immutable.Queue[Int] = Queue(2, 3)
Обратите внимание, что dequeue возвращает пару, состоящую из удаленного элемента и остальной части очереди.
Диапазоны (Ranges)
Диапазон
представляет собой упорядоченную последовательность целых чисел, которые отделены друг от друга одинаковыми размерами. Например, “1, 2, 3” - это диапазон, так же как и “5, 8, 11, 14”. Для создания диапазона в Scala используйте заготовленные методы to и by.
scala> 1 to 3
res2: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)
scala> 5 to 14 by 3
res3: scala.collection.immutable.Range = Range(5, 8, 11, 14)
Если вы хотите создать диапазон, исключающий верхнюю границу, то для удобства используйте метод until вместо to:
scala> 1 until 3
res2: scala.collection.immutable.Range = Range(1, 2)
Диапазоны занимают константный размер, потому что они могут быть определены только тремя цифрами: их началом, концом и значением шага. Благодаря этому представлению большинство операций на диапазонах выполняется очень быстро.
Compressed Hash-Array Mapped Prefix-trees
Хэш деревья - это стандартный способ эффективного создания неизменяемых множеств и ассоциативных массивов (мап). Compressed Hash-Array Mapped Prefix-trees - это специальные хэш деревья для JVM, которые улучшают локальность и обеспечивают компактную и элегантную реализацию деревьев. Они базируются на классе immutable.HashMap. Их представление очень похоже на реализацию векторов, которые также являются деревьями, где каждый узел имеет либо 32 элемента либо 32 поддерева. Но в данном случае ключ выбирается на основе хэш-кода. Например, чтобы найти ключ на мапе, сначала берут хэш-код ключа. Затем самые младшие 5 бит хэш-кода используются для выбора первого поддерева, за которым следуют следующие 5 бит и так далее. Выбор прекращается, когда для всех битов будут найдены ключи.
Хэш деревья пытаются предоставить разумный баланс между достаточно быстрым поиском и достаточно эффективными операциями вставки (+) и удаления (-) элементов. Именно поэтому они лежат в основе стандартных реализаций Scala неизменяемых множеств и ассоциативных массивов (мап). На самом деле, в Scala есть дополнительная оптимизация для неизменяемых множеств и мап, которые содержат менее пяти элементов. Множества и мапы от одного до четырех элементов хранятся как обычные объекты, которые содержат только элементы (или пары ключ/значение в случае мапы) как поля. Пустое неизменяемое множество и пустая неизменяемая мапа - это всегда объект-сингэлтон - нет необходимости размножать сущности для них, потому что пустое неизменяемое множество или мапа всегда будут оставаться пустыми.
Красно-Черные Деревья (Red-Black Trees)
Красно-черные деревья представляют собой разновидность сбалансированного двоичного дерева, где одни узлы помечаются как “красные”, а другие - как “черные”. Как и любое сбалансированное двоичное дерево, операции над ним занимают по времени логарифм от количества элементов дерева.
Scala предлагает реализацию неизменяемых множеств и мап, использующих красно-черное дерево, в классах TreeSet и TreeMap.
scala> scala.collection.immutable.TreeSet.empty[Int]
res11: scala.collection.immutable.TreeSet[Int] = TreeSet()
scala> res11 + 1 + 3 + 3
res12: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 3)
Красно-черные деревья - стандартная реализацией SortSet в Scala, поскольку они предоставляют эффективный итератор, который выдает все элементы в отсортированном порядке.
Неизменяемые Битовые Наборы (Immutable BitSets)
BitSet представляет собой набор маленьких целых чисел в виде набора битов большего целого числа. Например, набор битов, содержащий 3, 2 и 0, будет представлен как целое число 1101 в двоичном виде, т.е. 13 в десятичном.
Внутри битового набора используется массив 64-битных Longов. Первый Long в массиве для целых чисел от 0 до 63, второй для чисел от 64 до 127 и так далее. Таким образом, наборы битов очень компактны до тех пор, пока наибольшее целое число в наборе меньше нескольких сотен или около того.
Операции с битовым набором выполняются очень быстро. Проверка на наличие занимает постоянное время. Добавление элемента в набор занимает время, пропорциональное количеству Longов в массиве битов, которых обычно совсем не много. Вот несколько простых примеров использования битового набора:
scala> val bits = scala.collection.immutable.BitSet.empty
bits: scala.collection.immutable.BitSet = BitSet()
scala> val moreBits = bits + 3 + 4 + 4
moreBits: scala.collection.immutable.BitSet = BitSet(3, 4)
scala> moreBits(3)
res26: Boolean = true
scala> moreBits(0)
res27: Boolean = false
VectorMaps
VectorMap
представляет собой мапу, использующую и Vector ключей и HashMap. У него есть итератор, который возвращает все записи в порядке их вставки.
scala> val vm = scala.collection.immutable.VectorMap.empty[Int, String]
vm: scala.collection.immutable.VectorMap[Int,String] =
VectorMap()
scala> val vm1 = vm + (1 -> "one")
vm1: scala.collection.immutable.VectorMap[Int,String] =
VectorMap(1 -> one)
scala> val vm2 = vm1 + (2 -> "two")
vm2: scala.collection.immutable.VectorMap[Int,String] =
VectorMap(1 -> one, 2 -> two)
scala> vm2 == Map(2 -> "two", 1 -> "one")
res29: Boolean = true
Первые строки показывают, что содержимое VectorMap сохраняет порядок вставки, а последняя строка показывает, что VectorMap сравнимы с другими Map и что это сравнение не учитывает порядок элементов.
ListMaps
ListMap представляет собой мапу в виде связанного списка пар ключ-значение. В общем, операции на связанной мапе могут потребовать обхода по всему связанному списку. Таким образом, время выполнении обхода на связанной мапе линейно зависит от размера мапы. На самом деле, для связанных мапов в Scala практически нет вариантов для использования, так как стандартные мапы практически всегда быстрее. Единственным возможным исключением из этого, является то, что мапа по каким-либо причинам построена таким образом, что первые элементы в списке запрашиваются намного чаще, чем все остальные.
scala> val map = scala.collection.immutable.ListMap(1->"one", 2->"two")
map: scala.collection.immutable.ListMap[Int,java.lang.String] =
Map(1 -> one, 2 -> two)
scala> map(2)
res30: String = "two"