Битовый векторный вектор (он же постоянный вектор) - это структура данных, изобретенная Rich Hickey для Clojure, которая была внедрена в Scala с 2010 года (v 2.8).Это его умная побитовая индексация , которая обеспечивает высокоэффективный доступ и модификацию больших наборов данных.
Изменяемые векторы и списки массивов, как правило, представляют собой просто массивы, которые увеличиваются и уменьшаются при необходимости.Это прекрасно работает, когда вы хотите изменчивость, но это большая проблема, когда вы хотите постоянство.Вы получаете медленные операции модификации, потому что вам придется все время копировать весь массив, и он будет использовать много памяти.Было бы идеально избегать избыточности, насколько это возможно, без потери производительности при поиске значений наряду с быстрыми операциями.Это именно то, что делает постоянный вектор Clojure, и это делается через сбалансированные упорядоченные деревья.
Идея состоит в том, чтобы реализовать структуру, которая похожа на двоичное дерево.Единственное отличие состоит в том, что внутренние узлы в дереве имеют ссылку не более чем на два подузла и не содержат самих элементов.Узлы листа содержат не более двух элементов.Элементы расположены по порядку, что означает, что первый элемент является первым элементом в самом левом листе, а последний элемент является самым правым элементом в крайнем правом листе.На данный момент мы требуем, чтобы все конечные узлы были на одной глубине 2 .В качестве примера рассмотрим дерево ниже: в нем целые числа от 0 до 8, где 0 - первый элемент, а 8 - последний.Число 9 - это размер вектора:
Если бы мы хотели добавить новый элемент в конец этого вектора, и мы оказались в изменчивом миремы вставили бы 9 в самый правый конечный узел, например:
Но вот проблема: мы не можем этого сделать, если хотим быть постоянными,И это, очевидно, не сработало бы, если бы мы хотели обновить элемент!Нам необходимо скопировать всю структуру или хотя бы ее часть.
Чтобы минимизировать копирование при сохранении полного сохранения, мы выполняем копирование пути: Мы копируем все узлы на пути до значения, о котором мы говоримобновить или вставить, и заменить значение новым, когда мы внизу.Результат нескольких вставок показан ниже.Здесь вектор с 7 элементами имеет общую структуру с вектором с 10 элементами:
Узлы розового цвета распределяются между векторами, а коричневыеи синий являются отдельными.Другие векторы, которые не отображаются, могут также делить узлы с этими векторами.