Как реализованы неизменяемые индексированные последовательности Scala и какова сложность их операций?

Question

Я смутно припоминаю, что где-то читал, что операции неизменяемой индексированной последовательности Scala О (логарифм n), но основание логарифма достаточно велико, так что для всех практических целей операции почти такие же, как О(1).Это правда?

Как IndexedSeq реализовано для достижения этой цели?

Answer 1

Реализация по умолчанию immutable.IndexedSeq является Vector.Вот отрывок из соответствующая документация о его реализации:

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

immutable.HashSet и immutable.HashMap реализуются по аналогичной технологии.

Answer 2

IndexedSeq это Vector, который представляет собой древовидную структуру (на самом деле дерево) с разветвлением 32.Таким образом, не считая локальности памяти, вы никогда не превысите коэффициент O(log n) около 6 — сравните с двоичным деревом, где он колеблется от 1 до ~30.

Тем не менее, если вы также посчитаете локальность памяти, вы заметите огромную разницу между индексацией в вектор элемента 1G и вектор из 10 элементов.(Вы заметите довольно большую разницу с Array также.)