Скорость List и Vector в Scala зависит от типа операций, которые вы выполняете. Обе структуры — неизменяемые (immutable), но имеют разную внутреннюю архитектуру и разные целевые сценарии использования.

List: архитектура и особенности производительности

List — это односвязный список, построенный из узлов, где каждый элемент указывает на следующий (head :: tail). Это классическая структура в функциональном программировании.

Временные характеристики:

Где List быстрее:

• Когда часто добавляют элементы в начало.

• Когда обходится последовательность от начала до конца.

• При использовании рекурсии и pattern matching (head :: tail).

• При создании небольших, статичных списков.

Vector: архитектура и особенности производительности

Vector — это дерево с фиксированной шириной 32, то есть дерево, где каждый узел содержит до 32 дочерних элементов. Глубина дерева — log₃₂(n), что даже при миллионах элементов означает глубину 5–6 уровней.

Временные характеристики:

Где Vector быстрее:

• При доступе по индексу.

• При обновлении элементов по индексу.

• При балансированных вставках в начало и конец.

• При объединении и фильтрации больших коллекций.

• При распараллеливании (в ParVector).

Сравнение по операциям

Особенности работы GC и памяти

• List создаёт много маленьких объектов (Cons-ячейки). Это может приводить к большему количеству сборок мусора.

• Vector компактнее в памяти: хранит массивы с 32 ячейками, меньше объектов, более кэш-френдли.

• Vector чаще предпочтительнее в нагруженных и реактивных системах.

Пример на практике

val list = List(1, 2, 3)
val vector = Vector(1, 2, 3)
list(2) // медленно: O(n)
vector(2) // быстро: O(1)
val l2 = 0 :: list // быстро
val v2 = 0 +: vector // медленно (O(log n))

Что использовать в зависимости от задачи

Синтетические тесты

Для обработки списков длиной до 10 элементов List быстрее в большинстве операций. Однако при размере 1000+ элементов Vector резко обходит List при случайном доступе и модификациях.

val list = (1 to 1000000).toList
val vector = (1 to 1000000).toVector
val t1 = System.nanoTime(); list(999999); println(System.nanoTime() - t1)
val t2 = System.nanoTime(); vector(999999); println(System.nanoTime() - t2)

В этом тесте vector(999999) выполнится на порядки быстрее, чем list(999999).

Выводы по производительности

• List — лучше для неиндексируемых последовательных операций.

• Vector — лучше для общего случая, где нужны и доступ по индексу, и модификации.

• Для больших коллекций почти всегда Vector будет быстрее и эффективнее.

• List выигрывает только тогда, когда вы исключительно добавляете в начало и обрабатываете head/tail.