Vector

Vector - это индексируемая неизменяемая последовательность. "Индексируемая" часть описания означает, что она обеспечивает произвольный доступ и обновление за практически постоянное время, поэтому можно быстро получить доступ к элементам Vector по значению их индекса, например, получить доступ к listOfPeople(123_456_789).

В общем, за исключением той разницы, что (а) Vector индексируется, а List - нет, и (б) List имеет метод ::, эти два типа работают одинаково.

Вот несколько способов создания Vector:

val nums = Vector(1, 2, 3, 4, 5)
// nums: Vector[Int] = Vector(1, 2, 3, 4, 5)
val strings = Vector("one", "two")
// strings: Vector[String] = Vector("one", "two")
case class Person(name: String)
val people = Vector(
  Person("Bert"),
  Person("Ernie"),
  Person("Grover")
)
// people: Vector[Person] = Vector(
//   Person(name = "Bert"),
//   Person(name = "Ernie"),
//   Person(name = "Grover")
// )

Поскольку Vector неизменяем, в него нельзя добавить новые элементы. Вместо этого создается новая последовательность, с добавленными к существующему Vector в начало или в конец элементами.

Например, так элементы добавляются в конец:

val a = Vector(1,2,3)
// a: Vector[Int] = Vector(1, 2, 3)
val b = a :+ 4
// b: Vector[Int] = Vector(1, 2, 3, 4)
val c = a ++ Vector(4, 5)
// c: Vector[Int] = Vector(1, 2, 3, 4, 5)

А так - в начало Vector-а:

val a = Vector(1,2,3)
// a: Vector[Int] = Vector(1, 2, 3)
val b = 0 +: a
// b: Vector[Int] = Vector(0, 1, 2, 3)
val c = Vector(-1, 0) ++: a
// c: Vector[Int] = Vector(-1, 0, 1, 2, 3)

В дополнение к быстрому произвольному доступу и обновлениям, Vector обеспечивает быстрое добавление в начало и конец.

Подробную информацию о производительности Vector и других коллекций см. в характеристиках производительности коллекций.

Наконец, Vector в цикле for используется точно так же, как List, ArrayBuffer или любая другая последовательность:

val names = Vector("Joel", "Chris", "Ed")
// names: Vector[String] = Vector("Joel", "Chris", "Ed")
for name <- names do println(s"My name is $name")
// My name is Joel
// My name is Chris
// My name is Ed

Вектора представленны деревьями с высоким уровнем ветвления (уровень ветвления дерева или графа - это количество дочерних элементов у каждого узла). Каждый узел дерева содержит до 32-х элементов вектора или содержит до 32-х других узлов. Вектора с размером до 32-х элементов могут быть представлены одним узлом. Вектора с 32 * 32 = 1024 элементами могут быть представлены одним витком. Для векторов с \(2^{15}\) элементами достаточно двух переходов от корня дерева до конечного элемента узла, трех переходов - для векторов с \(2^{20}\) элементами, четырех переходов - для \(2^{25}\) элементами и пяти переходов для \(2^{30}\) элементами. Таким образом, для всех векторов разумных размеров выбор элемента включает до 5 простых выборок массивов. Именно это подразумевается, что доступ к элементам осуществляется с "практически постоянным временем".

Так же как и доступ к элементу, операция обновления в векторах занимает "практически" постоянное время. Добавление элемента в середину вектора может быть выполнено через копирование узла содержащего этот элемент и каждого ссылающегося на него узла, начиная от корня дерева. Это означает, что процесс обновления элемента создает от одного до пяти узлов, каждый из которых содержит до 32 элементов или поддеревьев. Это, конечно, дороже, чем просто обновление элемента в изменяемом массиве, но все же намного дешевле, чем копирование вообще всего вектора.

Поскольку вектора обладают хорошим балансом между быстрой случайной выборкой и быстрым случайным обновлением элементов, они используются в качестве реализации неизменяемых индексированных последовательностей:

collection.immutable.IndexedSeq(1, 2, 3)
// res2: IndexedSeq[Int] = Vector(1, 2, 3)

Ссылки: