Пакет scala.collection.immutable

Явное создание экземпляра интерфейса Map для уменьшения размера файла классов в подклассах.

Явное создание экземпляра интерфейса Seq для уменьшения размера файла классов в подклассах.

Явное создание экземпляра интерфейса Set для уменьшения размера файла классов в подклассах.

Неизменяемый массив.

Поддерживает эффективное индексированное обращение и имеет небольшой размер в памяти.

Класс для неизменяемых битовых наборов.

Битовые наборы — это наборы целых чисел без знака, которые представлены массивами переменного размера бит, упакованными в 64-битные слова. Размер памяти битового набора определяется наибольшим числом, хранящимся в нем.

Этот класс реализует неизменяемые карты, используя сжатое хэш-массивовое префиксное дерево. Дополнительные сведения см. в статье https://michael.steindorfer.name/publications/oopsla15.pdf.

Этот класс реализует неизменяемые множества, используя сжатое хэш-массивовое префиксное дерево. Дополнительные сведения см. в статье https://michael.steindorfer.name/publications/oopsla15.pdf.

Специализированная неизменяемая структура карты для целочисленных ключей, основанная на быстрых объединяемых целочисленных картах Окасаки и Гила. По сути, это trie, основанное на двоичных цифрах целых чисел.

Примечание: Этот класс, начиная с версии 2.8, в значительной степени устарел по сравнению с HashMap.

Трейт для коллекций, гарантированно неизменяемых.

Этот класс реализует неизменяемый связанный список, который вычисляет элементы в порядке и только при необходимости. Вот пример:

import scala.math.BigInt
object Main extends App {

  val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }

  fibs take 5 foreach println
}

// prints
//
// 0
// 1
// 1
// 2
// 3

Элементы LazyList запоминаются в кэше; то есть, значение каждого элемента вычисляется только один раз. Чтобы проиллюстрировать, мы изменим тело fibs значение выше и возьмём ещё несколько значений:

import scala.math.BigInt
object Main extends App {

  val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(
    fibs.tail).map(n => {
      println("Adding %d and %d".format(n._1, n._2))
      n._1 + n._2
    })

  fibs take 5 foreach println
  fibs take 6 foreach println
}

// prints
//
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

// And then prints
//
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

Существует ряд тонких моментов в приведенном примере.

Определение fibs является val, а не методом. Кеширование LazyList требует, чтобы у нас было место для хранения информации, а val позволяет нам это сделать. Хотя LazyList фактически изменяется при доступе, это не меняет концепции его неизменяемости. После запоминания значения они не изменяются, а значения, которые ещё не были запомнены, всё ещё "существуют", просто они ещё не были реализованы.Следует быть осторожными с кэшированием; вы очень быстро можете израсходовать большое количество памяти, если не будете осторожны. Причиной этого является то, что кэширование LazyList создаёт структуру, очень похожую на scala.collection.immutable.List. Пока что-то держит голову, голова держит хвост, и так далее рекурсивно. С другой стороны, если ничего не держит голову (например, мы использовали def для определения LazyList), то как только она больше не используется непосредственно, она исчезает.Обратите внимание, что некоторые операции, включая drop, dropWhile, flatMap или collect могут обработать большое количество промежуточных элементов перед возвратом. Они обязательно удерживают голову, так как являются методами LazyList, а ленивый список держит свою собственную голову. Для вычислений такого типа, где кэширование нежелательно, используйте Iterator когда это возможно.

// For example, let's build the natural numbers and do some silly iteration
// over them.

// We'll start with a silly iteration
def loop(s: String, i: Int, iter: Iterator[Int]): Unit = {
  // Stop after 200,000
  if (i < 200001) {
    if (i % 50000 == 0) println(s + i)
    loop(s, iter.next(), iter)
  }
}

// Our first LazyList definition will be a val definition
val lazylist1: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}

// Because lazylist1 is a val, everything that the iterator produces is held
// by virtue of the fact that the head of the LazyList is held in lazylist1
val it1 = lazylist1.iterator
loop("Iterator1: ", it1.next(), it1)

// We can redefine this LazyList such that all we have is the Iterator left
// and allow the LazyList to be garbage collected as required.  Using a def
// to provide the LazyList ensures that no val is holding onto the head as
// is the case with lazylist1
def lazylist2: LazyList[Int] = {
  def loop(v: Int): LazyList[Int] = v #:: loop(v + 1)
  loop(0)
}
val it2 = lazylist2.iterator
loop("Iterator2: ", it2.next(), it2)

// And, of course, we don't actually need a LazyList at all for such a simple
// problem.  There's no reason to use a LazyList if you don't actually need
// one.
val it3 = new Iterator[Int] {
  var i = -1
  def hasNext = true
  def next(): Int = { i += 1; i }
}
loop("Iterator3: ", it3.next(), it3)

Тот факт, что tail работает вообще, вызывает интерес. В определении fibs у нас есть начальное (0, 1, LazyList(...)), поэтому tail детерминировано. Если бы мы определили fibs, так что только 0 были бы конкретно известны, то действие определения tail потребовало бы оценки tail, что вызвало бы бесконечную рекурсию и переполнение стека. Если мы определим определение, где хвост изначально не вычисляется, то у нас будет бесконечная рекурсия:

// The first time we try to access the tail we're going to need more
// information which will require us to recurse, which will require us to
// recurse, which...
lazy val sov: LazyList[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 }

Определение fibs выше создаёт больше объектов, чем необходимо, в зависимости от того, как вы хотите его реализовать. Следующая реализация обеспечивает более "эффективную" реализацию из-за того, что у неё есть более прямой путь к самим числам:

lazy val fib: LazyList[Int] = {
  def loop(h: Int, n: Int): LazyList[Int] = h #:: loop(n, h + n)
  loop(1, 1)
}

Класс неизменяемых связанных списков, представляющих упорядоченные коллекции элементов типа A.

Этот класс поставляется с двумя реализующими case-классами scala.Nil и scala.::, которые реализуют абстрактные члены isEmpty, head и tail.

Этот класс оптимален для шаблонов доступа «последний вошел — первый вышел» (LIFO), подобных стеку. Если вам нужен другой шаблон доступа, например, случайный доступ или FIFO, рассмотрите использование коллекции, более подходящей для этого, чем List.

Производительность

Время: List имеет O(1) добавление в начало и доступ к голове/хвосту. Большинство других операций зависят от O(n) количества элементов в списке. Это включает индексный поиск элементов, length, append и reverse.

Память: List реализует структурное совместное использование хвостового списка. Это означает, что многие операции имеют стоимость, либо нулевую, либо постоянную.

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

Этот класс реализует неизменяемые карты, используя структуру данных на основе списка. Итераторы и методы обхода карты ListMap посещают пары ключ-значение в порядке их первоначального вставки.

Элементы хранятся во внутренней обратной последовательности вставки, то есть самый последний ключ находится в голове списка. Таким образом, такие методы, как head и tail, имеют сложность O(n), в то время как last и init имеют сложность O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого количества элементов.

Экземпляры ListMap представляют пустые карты; они могут быть созданы, либо напрямую вызвав конструктор, либо применив функцию ListMap.empty.

Этот класс реализует неизменяемые множества, используя структуру данных на основе списка. Итераторы и методы обхода множества ListSet посещают элементы в порядке их первоначального вставки.

Элементы хранятся во внутренней обратной последовательности вставки, то есть самый последний элемент находится в голове списка. Таким образом, такие методы, как head и tail, имеют сложность O(n), в то время как last и init имеют сложность O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого количества элементов.

Экземпляры ListSet представляют пустые множества; они могут быть созданы, либо напрямую вызвав конструктор, либо применив функцию ListSet.empty.

Специализированная неизменяемая структура отображения для ключей типа long, основанная на быстрых объединяемых картах long Okasaki и Gill. По существу, это дерево, основанное на двоичных цифрах целых чисел.

Примечание: Этот класс с версии 2.8 в значительной степени устарел по сравнению с HashMap.

NumericRange — более обобщённая версия класса Range, работающая с произвольными типами. Она требует реализации типа диапазона.

Фабрики для распространённых типов включают в себя ..., ..., и ... . ... существует для полноты, но основанный на ... диапазон должен быть более производительным.

val r1 = Range(0, 100, 1)
val veryBig = Int.MaxValue.toLong + 1
val r2 = Range.Long(veryBig, veryBig + 100, 1)
assert(r1 sameElements r2.map(_ - veryBig))

Queue объекты реализуют структуры данных, которые позволяют вставлять и извлекать элементы в порядке очереди (FIFO).

Queue реализуется как пара List списков, один содержащий элементы ввод, а другой — элементы вывод. Элементы добавляются в список ввод и удаляются из списка вывод. Когда список вывод пустеет, очередь поворачивается путем замены списка вывод на in.reverse, а in на Nil.

Добавление элементов в очередь всегда имеет стоимость O(1). Удаление элементов имеет стоимость O(1), за исключением случаев, когда требуется поворот, в этом случае взимается стоимость O(n), где n — количество элементов в очереди. Когда это происходит, n операций удаления со стоимостью O(1) гарантированы. Удаление элемента в среднем составляет O(1).

Класс Range представляет целые значения в диапазоне [start;end) с ненулевым значением шага step. Это специальный случай индексированной последовательности. Например:

val r1 = 0 until 10
val r2 = r1.start until r1.end by r1.step + 1
println(r2.length) // = 5

Диапазоны, содержащие более Int.MaxValue элементов, могут быть созданы, но эти переполненные диапазоны имеют ограниченные возможности. Любой метод, который может потребовать создания коллекции длиной более Int.MaxValue элементов, или может быть попрошен индексировать сверх Int.MaxValue элементов, выбросит исключение. Переполненные диапазоны могут безопасно быть уменьшены в размере путем изменения размера шага (например, by 3) или взятия/удаления элементов. contains, equals, и доступ к концам диапазона (head, last, tail, init) также разрешены для переполненных диапазонов.

Общий интерфейс для упорядоченных неизменяемых карт. Конкретные классы должны предоставить функциональность для абстрактных методов в SeqMap.

Обратите внимание, что при проверке на равенство SeqMap не учитывает порядок.

Неизменяемая карта, пары ключ-значение которой отсортированы в соответствии с порядком scala.math.Ordering по ключам.

Позволяет выполнять запросы по диапазонам к своим ключам, и реализации должны гарантировать, что обход происходит в отсортированном порядке, в соответствии с scala.math.Ordering карты.

Неизменяемый отсортированный список (SortedMap), значения которого хранятся в красно-чёрном дереве.

Этот класс оптимален, когда будут выполняться запросы по диапазону или когда требуется обход в порядке сортировки. Если вам нужны только поиски по ключу и порядок обхода значений по ключу не важен, рассмотрите использование * scala.collection.immutable.HashMap, который, как правило, имеет лучшую производительность. Если вам нужен порядок вставки, рассмотрите * scala.collection.immutable.SeqMap, для которого не требуется указание порядка.

Этот класс реализует неизменяемую карту, сохраняющую порядок, используя хэш-таблицу для сопоставления ключей со значениями, обеспечивая эффективный поиск, и дерево для упорядочивания ключей, обеспечивая эффективный обход и деструктуризацию в порядке вставки/модификации.

По умолчанию используется порядок вставки (TreeSeqMap.OrderBy.Insertion), но вместо него можно использовать порядок модификации (TreeSeqMap.OrderBy.Modification), если это указано при создании.

Метод orderingBy(orderBy: TreeSeqMap.OrderBy): TreeSeqMap[K, V] можно использовать для переключения на указанный порядок для возвращаемой карты.

Ключ можно вручную обновить (т.е. поместить в конец) с помощью метода refresh(key: K): TreeSeqMap[K, V] (независимо от используемого порядка).

Внутренне счётчик порядкового номера увеличивается для каждой вставки/модификации, а затем текущий порядковый номер используется в качестве ключа в дереве отображений. После 2³² вставок/модификаций вся карта копируется (при этом сбрасывается счётчик порядковых номеров).

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

Вектор — это универсальная неизменяемая структура данных. Она обеспечивает произвольный доступ и обновления за время, эффективно равное константе, а также очень быстрые добавление в начало и в конец. Поскольку векторы хорошо сочетают быстрый произвольный выбор и быстрые произвольные функциональные обновления, они в настоящее время являются реализацией по умолчанию для неизменяемых индексированных последовательностей. Он подкреплён little endian bit-mapped vector trie с разветвлением 32. Локальность очень хорошая, но не непрерывная, что хорошо для очень больших последовательностей.

Класс для построения экземпляров Vector. Этот билдер является повторно используемым.

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

В отличие от ListMap, VectorMap имеет амортизированную эффективно постоянную выборку, за счет использования дополнительной памяти и, как правило, более низкой производительности для других операций

Этот класс служит оболочкой, дополняющей строки всеми операциями, которые есть в индексированных последовательностях.

Разница между этим классом и StringOps заключается в том, что вызов методов трансформации, таких как filter и map, приведет к объекту типа WrappedString, а не String.