Списки очень эффективны, когда алгоритм, обрабатывающий их, тщательно обрабатывает их головы. Доступ, добавление и удаление головы списка занимает только постоянное время, в то время как доступ или изменение других элементов в списке занимает время, линейное, пропорциональное длине списка.
Вектор - это тип коллекции (представленный в Scala 2.8), который учитывает неэффективность для случайного доступа к спискам. Векторы позволяют получить доступ к любому элементу списка в «эффективном» постоянном времени. Это большая константа, чем для доступа к заголовку списка или для чтения элемента массива, но тем не менее он постоянный. В результате, алгоритмы, использующие векторы, не должны быть осторожны при доступе только к голове последовательности. Они могут получать доступ и изменять элементы в произвольных местах.
Векторы строятся и модифицируются так же, как и любая другая последовательность.
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 примитивных массивов. Это то, что мы имели в виду, когда мы писали, что доступ к элементу является «эффективным
постоянным временем».
Векторы неизменяемы, поэтому вы не можете изменить элемент вектора и сохранить новый вектор. Однако с помощью updated
метода вы можете создать новый вектор, который отличается от заданного вектора только в одном элементе:
scala> val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)
scala> vec updated (2, 4)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)
scala> vec
res1: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)Как показывает последняя строка выше, вызов updated не влияет на исходный вектор vec. Подобно выбору, обновление
функциональных векторов также является «эффективным постоянным временем». Обновление элемента в середине вектора может
быть выполнено путем копирования узла, содержащего элемент, и каждого узла, который указывает на него, начиная с корня дерева.
Это означает, что функциональное обновление создает от одного до пяти узлов, каждый из которых содержит до 32 элементов
или поддеревьев. Это, конечно, дороже, чем обновление на месте в изменяемом массиве, но все же намного дешевле, чем
копирование всего вектора.
Поскольку векторы обеспечивают хороший баланс между быстрыми случайными выборами и быстрыми случайными функциональными обновлениями, в настоящее время векторы являются реализацией неизменяемых индексированных последовательностей по умолчанию:
scala> collection.immutable.IndexedSeq(1, 2, 3)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)Если этот проект окажется полезным тебе - нажми на кнопочку ★ в правом верхнем углу.