Эта статьяГлубокое погружение в immutable.jsВторой в серии.

Подробное изучение механизма реализации immutable.js (1)

Подробное изучение механизма реализации immutable.js (2) Эта статья

В предыдущей статье мы изучили базовый принцип реализации постоянной структуры данных Immutable.js и ее основную структуру данных.Vector Trieвведены и сосредоточены на位分区механизм. использовать位分区Основная причина заключается в оптимизации скорости, а для оптимизации пространства, как это делает Immutable.js? Давайте сначала обсудим это.

HAMT

HAMTполное имяhash array mapped trie, его основной принцип тот же, что и в предыдущей статьеVector TrieОчень похоже, но дерево сжимается для экономии места. Ссылка на Immutable.jsHAMTДерево сжато по высоте и внутри узлов.

сжатие высоты дерева

Предположим, у нас есть 2 зубцаVector Trie, теперь значение сохраняется, ключ110(двоичная форма), она будет храниться в0 1 1По этому пути, как показано ниже:

Очевидно, структура, показанная на этом рисунке, была оптимизирована самым простым образом, потому что теперь хранится только одно значение, поэтому поместите его с110Неактуальные узлы удаляются. Что еще можно оптимизировать? Мы обнаружили, что два узла посередине также можно удалить, как показано ниже:

При получении этого значения мы начинаем с0Найдите его и обнаружите, что это непосредственно корневой узел, затем просто возьмите значение, которое он хранит. Другими словами, мы можем использовать как можно меньше двоичных битов для идентификации ключа, не вызывая путаницы. Таким образом, мы имеем высокую степень сжатия, что сокращает пространство и время на поиск и модификацию.
Если значение должно быть добавлено, его ключ также заканчивается0,Как я должен это делать? Очень просто, как показано ниже:

Мы просто добавляем или вычитаем узлы по мере необходимости.

Внутреннее сжатие узла — растровое изображение

В предыдущей статье мы упоминали, что в Trie of Immutable.js длина каждого массива узлов равна 32. Однако во многих случаях большая часть из этих 32 позиций не используется, и такой большой массив явно занимает много места. космос большое пространство. использоватьBitmap, мы можем сжать массив.
Возьмем пример массива длиной 8:

На самом деле мы просто используем нижний индекс массива для индексации ключа, поэтому 5-й, 6-й и 7-й биты массива, очевидно, в настоящее время бесполезны, а как насчет 0, 2 и 3? Должны ли мы поддерживать массив длины 5 для индекса 4? Нам нужно только указать, что учитываются позиции с индексами 1 и 4 в «воображаемом массиве». можно использовать здесьbitmap,следующим образом:

Мы используем число, чтобы выразить ситуацию-заполнитель в «воображаемом массиве длины 8» в его двоичной форме: 1 означает, что соответствующая позиция нижнего индекса в массиве имеет значение, а 0 означает, что соответствующая позиция пуста. Например, 4-й бит этого двоичного числа (считая справа налево, начиная с 0) теперь равен 1, что означает, что на позиции индекса 4 массива есть значение. Таким образом, массив длины 8 можно сжать до 2.
Обратите внимание, что элементы в этом массиве по-прежнему расположены в порядке «воображаемого массива», поэтому, когда мы хотим взять элемент с индексом i в «воображаемом массиве», первое, что нужно сделать, это определить, существует ли значение в позиции, если да, то следующим шагом является получение количества элементов перед ним, то есть сколько битов стоит 1 перед i-м битом в двоичном числе. Предположим, число равно a, тогда индекс элемента в текущем сжатом массиве равен a.
В конкретных операциях мы можемbitmap & (1 << i - 1), получаем двоичное число, в двоичном числе только место, где стоит значение до i-го бита, равно 1, а все остальные 0. Далее нам нужно только посчитать число 1 в двоичном числе чтобы получить индекс. Процесс подсчета количества единиц в двоичном числе называетсяpopcount,Есть много специфических алгоритмов,мало в этом разбираюсь,поэтому расширять не буду.После клика на лоб,это адрес вики.Если интересно,можете изучить.
Давайте посмотрим на исходный код этой части:

get(shift, keyHash, key, notSetValue) {
  if (keyHash === undefined) {
    keyHash = hash(key);
  }
  const bit = 1 << ((shift === 0 ? keyHash : keyHash >>> shift) & MASK);
  const bitmap = this.bitmap;
  return (bitmap & bit) === 0
    ? notSetValue
    : this.nodes[popCount(bitmap & (bit - 1))].get(
        shift + SHIFT,
        keyHash,
        key,
        notSetValue
      );
}

function popCount(x) {
  x -= (x >> 1) & 0x55555555;
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f;
  x += x >> 8;
  x += x >> 16;
  return x & 0x7f;
}

почему 32

В прошлой статье мы упомянули, что Vector Trie Immutable.js использует 32 в качестве длины массива, а также объяснили, что из-за использования位分区, число может быть только степенью 2, поэтому оно не может быть 31, 33 и т. д. А как же 8, 16, 64 и т.д.? Это достигается путем реальных испытаний, см. рисунок ниже:

График для времени поиска и обновления, вроде 8 или 16 лучше? Учитывая, что при обычном использовании частота поиска намного выше частоты обновления, поэтому Immutable.js выбрал 32.

рассмотрение

Теперь мы можем понять скриншот из начала первой статьи:


Мы видим, что на карте в основном три типа узлов:

• HashArrayMapNode, имеет количество дочерних узлов > 16 и имеет длину массива 32
• BitmapIndexedNode, количество принадлежащих дочерних узлов ≤16 , длина принадлежащего массива равна количеству дочерних узлов, сжатых по битовому массиву
• ValueNode, конечный узел, хранить ключ и значение

Кроме того, каждый узел, по-видимому, имеетownerIDсвойства, что это делает? Он включает в себя изменяемые структуры данных в Immutable.js.

Transient

Фактически можно сказать, что структура данных в Immutable.js имеет две формы: «неизменяемая» и «изменяемая». В то время как «неизменяемость» является основным преимуществом Immutable.js, операции в «изменяемой» форме, конечно, более эффективны. Иногда для определенной серии операций нам нужно получить состояние только после завершения группы операций, очевидно, что избыточно, если каждая операция в середине реализована с неизменяемыми структурами данных. В этом случае мы можем использоватьwithMutationsМетод выполняет временную «изменяемую» операцию над соответствующей структурой данных и, наконец, возвращает неизменяемую структуру, котораяTransient, например:

let map = new Immutable.Map({});
map = map.withMutations((m) => {
  // 开启Transient
  m.set('a', 1); // 我们可以直接在m上进行修改，不需要 m = m.set('a', 1)
  m.set('b', 2);
  m.set('c', 3);
});
// Transient结束

1. узла для работыownerIDЕсли он несовместим с родительским узлом, создается новый узел, а значение старого узла копируется.ownerIDОбновление до родительского узлаownerID, а затем выполнить соответствующие операции;
2. узла для работыownerIDВ соответствии с родительским узлом работать непосредственно с этим узлом;

function OwnerID() {}

function asMutable() {
  return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
}

function withMutations(fn) {
  const mutable = this.asMutable();
  fn(mutable);
  return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
}

update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) {
  // ...省略前面的代码
  const isEditable = ownerID && ownerID === this.ownerID;
  const newNodes = setAt(nodes, idx, newNode, isEditable);

  if (isEditable) {
    this.count = newCount;
    this.nodes = newNodes;
    return this;
  }

  return new HashArrayMapNode(ownerID, newCount, newNodes);
}

let map = new Immutable.Map({});

for (let i = 0; i < 10; i++) {
  map = map.set(Math.random(), i); // 随便塞一点别的数据
}

map = map.set('abc', 'value1');
map = map.set('bCc', 'value2');

console.log(map)