Эта статья - то, что я обновляюГлубокое погружение в immutable.jsПервый в серии.

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

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

Immutable.js тратит много удобства на Facebook в течение 3 лет и предоставляет много удобства для фронтенд-разработки. Мы знаем, что Immutable.js принимает持久化数据结构, Чтобы гарантировать неизменность каждого объекта, любая операция добавления, изменения или удаления будет генерировать новый объект, а结构共享и другие способы значительно улучшить производительность.

В Интернете есть много статей, которые кратко знакомят с принципами работы с Immutable.js, но большинство из них — просто царапины.Есть несколько статей о реализации персистентных структур данных в Clojure или Go. Следующее объединяет различные источники, исходный код Immutable.js и мое собственное понимание для более глубокого изучения механизма реализации Immutable.js.

Эта серия статей может быть самой подробной и всеобъемлющей о принципах Immutable.js Добро пожаловать, чтобы поставить лайк и собрать σ`∀´)σ.

простой пример

Прежде чем углубиться в это, давайте рассмотрим простой пример:

let map1 = Immutable.Map({});

for (let i = 0; i < 800; i++) {
  map1 = map1.set(Math.random(), Math.random());
}

console.log(map1);

Этот код последовательно записывает в карту 800 пар случайно сгенерированных ключей и значений. Давайте сначала посмотрим на вывод консоли и получим общее представление о ее структуре данных (достаточно беглого взгляда):

Вы можете видеть, что это древовидная структура, а дочерние узлы размещены в свойстве `nodes` в виде массива. Максимальная длина `nodes`, кажется, равна 32. Люди, знакомые с растровыми изображениями, могли догадаться, что здесь делает свойство `bitmap`, оно включает в себя сжатие ширины дерева, о чем будет рассказано позже.

Этот `ValueNode` хранит набор значений, `entry[0]` — это ключ, а `entry[1]` — это значение.

Пока достаточно приблизительно посмотреть на форму, далее будем постепенно приоткрывать ее завесу от мелкого к глубокому. (Все свойства на графике будут объяснены во второй статье)

Фундаментальный

Давайте посмотрим на вики для持久化数据结构Определение:

In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified.

Простое объяснение заключается в том, что для持久化数据结构После каждой модификации мы получим новую версию, а старая версия может быть сохранена не повреждена.

Immutable.js реализован с деревьями持久化数据结构, сначала посмотрите на дерево ниже:

если бы мы былиgВставьте узел нижеh, как сохранить исходное дерево без изменений после вставки? Самый простой способ, конечно, перестроить дерево:

Но это заведомо неэффективно.Каждая операция должна генерировать новое дерево, что занимает много времени и места.Поэтому предлагается следующая схема оптимизации:

Мы генерируем новый корневой узел. Для измененной части регенерируем все узлы на соответствующем пути. Для части, которая не была изменена в этой операции, мы можем напрямую скопировать соответствующий старый узел. Это на самом деле结构共享. Таким образом, каждая операция также получит новую версию (корневой узел изменился, новыйa!== старыйa), исторические версии можно сохранить без изменений, сэкономив при этом место и время.

До сих пор мы обнаружили, что использование дерева для достижения持久化数据结构Все еще относительно простой, Immutable.js предоставляет различные структуры данных, например, вернемся к началу примера, как карта становится持久化数据结构Шерстяная ткань?

Vector Trie

На самом деле, для карты мы можем думать о ней как о плоском дереве, что совпадает с приведенной выше реализацией.持久化数据结构Точно так же после каждой операции генерируется новый объект, по очереди копируются все старые значения и перегенерируются свойства, которые необходимо изменить или добавить. Это на самом делеObject.assign, но это явно неэффективно, есть ли лучший способ?

в реализации持久化数据结构, ссылка на Immutable.jsVector TrieЭта структура данных (на самом деле более точное названиеpersistent bit-partitioned vector trieилиbitmapped vector trie, которая представляет собой структуру данных, используемую в Clojure, соответствующая реализация в Immutable.js очень похожа), давайте сначала разберемся с ее базовой структурой.

Если у нас есть карта, ключи все номера (конечно, вы также можете понять это как массив){0: ‘banana’, 1: ‘grape’, 2: ‘lemon’, 3: ‘orange’, 4: ‘apple’}, чтобы построить бинарное деревоVector Trie, мы можем сначала преобразовать все ключи в двоичную форму:{‘000’: ‘banana’, ‘001’: ‘grape’, ‘010’: ‘lemon’, ‘011’: ‘orange’, ‘100’: ‘apple’}, а затем создайте, как показано нижеVector Trie:

можно увидеть,Vector TrieКаждый узел - это массив0и1Два числа, представляющие собой двоичное число, все значения хранятся на листовых узлах, например, ищем001значение, просто следуйте0 0 1найти его, вы можете получитьgrape. тогда хочу добиться持久化数据结构Конечно это не сложно, например мы хотим добавить5: ‘watermelon’:

Видно, что для карты, ключами которой являются все числа, мы можем полностью передать картуVector Trieдобиться этого, достигнув持久化数据结构. Что делать, если ключ не является числом? Просто используйте механизм сопоставления, чтобы преобразовать его в число. Immutable.js реализуетhashФункция, которая преобразует значение в соответствующее число.

Чтобы упростить здесь, длина каждого массива узлов составляет всего 2, поэтому при большом количестве данных дерево станет очень глубоким, а запрос будет трудоемким, поэтому длину массива можно увеличить. Immutable.js выбрал 32. Почему не 31?40? На самом деле длина массива должна быть целой степенью числа 2, что предполагает реализациюVector TrieОптимизация времени, давайте сначала изучим это.

Некоторое из следующего содержания может быть относительно сложным для тех, кто не знаком с базовым преобразованием и манипулированием битами, но его можно понять, если хорошенько подумать.

Разделение цифр

数字分区Это означает, что мы сопоставляем ключ как число с деревом префиксов, как описано в предыдущем разделе.

Если у нас есть ключ9128, с основанием 7, то есть длина массива 7, он находится вVector TrieВот что он говорит:

Нам нужно 5 слоев массивов, сначала находим3эту ветку, а затем найти5, с последующим0. Чтобы получить эти числа последовательно, мы можем добавить9128преобразовать в 735420, но в этом нет необходимости, потому что процесс преобразования в шестнадцатеричный вид заключается в непрерывном делении и взятии остатка, чтобы получить число по каждой цифре, нам не нужно заранее преобразовывать его, и аналогичные операции можно выполнить над каждый слой по очереди.

Используя знания, связанные с базовым преобразованием, мы можем использовать этот метод key / radix^{level - 1}% системы счисления, чтобы получить каждую цифру (Для краткости в этой статье все, кроме кода/Все символы обозначают деление и округление в меньшую сторону.),вradixдлина каждого слоя массива, то есть преобразованная в несколько знаков после запятой,levelЭто текущее количество слоев, то есть количество цифр. как здесьkeyда9128,radixда7, с началаlevelда5, по этой формуле мы можем получить номер первого слоя3.

Код реализован следующим образом:

const RADIX = 7;

function find(key) {
  let node = root; // root是根节点，在别的地方定义了

  // depth是当前树的深度。这种计算方式跟上面列出的式子是等价的，但可以避免多次指数计算。这个size就是上面的radix^level - 1
  for (let size = Math.pow(RADIX, (depth - 1)); size > 1; size /= RADIX) {
    node = node[Math.floor(key / size) % RADIX];
  }

  return node[key % RADIX];
}

const BITS = 5;
const WIDTH = 1 << BITS, // 25 = 32
const MASK = WIDTH - 1; // 31，即11111

function find(key) {
  let node = root; 

  for (let bits = (depth - 1) * BITS; bits > 0; bits -= BITS) {
    node = node[(key >>> bits) & MASK];
  }

  return node[key & MASK];
}

get(shift, keyHash, key, notSetValue) {
  if (keyHash === undefined) {
    keyHash = hash(key);
  }
  const idx = (shift === 0 ? keyHash : keyHash >>> shift) & MASK;
  const node = this.nodes[idx];
  return node
    ? node.get(shift + SHIFT, keyHash, key, notSetValue)
    : notSetValue;
}