Analyse détaillée du type List du code source d'Immutable.js (avec exemples)

Cet article vous apporte une analyse détaillée du type de liste du code source d'Immutable.js (avec des exemples). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Diagramme de stockage

J'utilise le code suivant comme exemple pour dessiner la structure de stockage de cette liste :

let myList = [];
for(let i=0;i<p><span class="img-wrap"><img src="https://img.php.cn//upload/image/772/741/819/1543214651133724.png" title="1543214651133724.png" alt="Analyse détaillée du type List du code source dImmutable.js (avec exemples)"></span></p><p><strong>2. Le processus de construction du trie vectoriel </strong></p><p>Nous utilisons le code ci-dessus comme exemple pour analyser étape par étape. La première étape consiste à convertir la liste native en un type de liste inmuable : </p><pre class="brush:php;toolbar:false">export class List extends IndexedCollection {
  // @pragma Construction

  constructor(value) { // 此时的value就是上面的myList数组
    const empty = emptyList();
    if (value === null || value === undefined) {//判断是否为空
      return empty;
    }
    if (isList(value)) {//判断是否已经是imutable的list类型
      return value;
    }
    const iter = IndexedCollection(value);//序列化数组
    const size = iter.size;
    if (size === 0) {
      return empty;
    }
    assertNotInfinite(size);
    if (size > 0 && size  {
      list.setSize(size);
      iter.forEach((v, i) => list.set(i, v));
    });
  }

  。。。。。。

}

Tout d'abord, une liste vide sera créée

let EMPTY_LIST;
export function emptyList() {
  return EMPTY_LIST || (EMPTY_LIST = makeList(0, 0, SHIFT));
}

La valeur de SHIFT est 5, export const SHIFT = 5 ; // Vous avez obtenu les meilleures performances après ______ ?

Continuez à regarder makeList et vous pouvez voir clairement les principales parties de la liste :

function makeList(origin, capacity, level, root, tail, ownerID, hash) {
  const list = Object.create(ListPrototype);
  list.size = capacity - origin;// 数组的长度
  list._origin = origin;// 数组的起始位置 一般是0
  list._capacity = capacity;// 数组容量 等于 size
  list._level = level;//树的深度，为0时是叶子结点。默认值是5，存储指数部分，用于方便位运算,增加一个深度，level值+5
  list._root = root;// trie树实现
  list._tail = tail;// 32个为一组，存放最后剩余的数据 其实就是 %32
  list.__ownerID = ownerID;
  list.__hash = hash;
  list.__altered = false;
  return list;
}

Sérialisez les données entrantes

// ArraySeq
iter = {
size: 数组的length,
_array: 传入数组的引用
}

Déterminez si la taille dépasse 32, taille > 0 && taille

_root et _tail ont la structure suivante :

// @VNode class
constructor(array, ownerID) {
  this.array = array;
  this.ownerID = ownerID;
}

Vous pouvez les déboguer et les afficher comme ceci :

let myList = [];
for(let i=0;i<p>taille si elle dépasse 32</p><pre class="brush:php;toolbar:false">return empty.withMutations(list => {
    list.setSize(size);//构建树的结构 主要是计算出树的深度
    iter.forEach((v, i) => list.set(i, v));//填充好数据
});

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

Il existe une méthode importante setListBounds dans list.setSize(size). Ci-dessous, nous examinons principalement comment cette méthode construit cet arbre

La fonction principale de cette méthode est de déterminer le niveau de la liste

function setListBounds(list, begin, end) {

  ......
  
  const newTailOffset = getTailOffset(newCapacity);

  // New size might need creating a higher root.
  // 是否需要增加数的深度 把 1 左移 newLevel + SHIFT 位 相当于 1 * 2 ^ (newLevel + SHIFT)
  // 以 size为 1100 为例子 newTailOffset的值为1088 第一次 1088 > 2 ^ 10 树增加一层深度
  // 第二次 1088 = 1 <pre class="brush:php;toolbar:false">function getTailOffset(size) {
    // (1100 - 1) / 2^5 % 2^5 = 1088
    return size >> SHIFT) <p>La structure construite via list.setSize(size);</p><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Analyse détaillée du type List du code source dImmutable.js (avec exemples)"></span></p><p> <strong>3. set La méthode </strong></p><p>listiter.forEach((v, i) => list.set(i, v)); ></p> ici. Voyons comment la méthode set définit les données <p></p><pre class="brush:php;toolbar:false">set(index, value) {
    return updateList(this, index, value);
}

function updateList(list, index, value) {
  ......
  if (index >= getTailOffset(list._capacity)) {
    newTail = updateVNode(newTail, list.__ownerID, 0, index, value, didAlter);
  } else {
    newRoot = updateVNode(
      newRoot,
      list.__ownerID,
      list._level,
      index,
      value,
      didAlter
    );
  }

  ......

}

function updateVNode(node, ownerID, level, index, value, didAlter) {
  // 根据 index 和 level 计算 数据set的位置在哪
  const idx = (index >>> level) & MASK;

  // 利用递归 一步一步的寻找位置 直到找到最终的位置
  if (level > 0) {
    const lowerNode = node && node.array[idx];
    const newLowerNode = updateVNode(
      lowerNode,
      ownerID,
      level - SHIFT,
      index,
      value,
      didAlter
    );
    ......
    // 把node节点的array复制一份生成一个新的节点newNode editableVNode函数见下面源码
    newNode = editableVNode(node, ownerID);
    // 回溯阶段将 子节点的引用赋值给自己
    newNode.array[idx] = newLowerNode;
    return newNode;
  }
  ......
  newNode = editableVNode(node, ownerID);
  // 当递归到叶子节点 也就是level <pre class="brush:php;toolbar:false">function editableVNode(node, ownerID) {
  if (ownerID && node && ownerID === node.ownerID) {
    return node;
  }
  return new VNode(node ? node.array.slice() : [], ownerID);
}

Regardons les résultats de l'exécution

une foisset(0,0)

Une fois la structure entière construite

Regardons l'ensemble de la liste nous venons de construire (1000, 'Remm'), en fait, le code source de tous les ensembles a été analysé ci-dessus, revoyons-le à nouveau.

Appelez la méthode set ci-dessus, index=1000, value='Remm'. Appelez updateList, puis appelez updateVNode. Calculez la position du nœud que vous recherchez par const idx = (index >>> level) & MASK; (dans cet exemple, les valeurs de idx sont 0->31->8). Recherche récursive continue, lorsque le niveau Liste mise à jour :

4. Obtenir la méthode

Compris la liste ci-dessus la construction et l'ensemble, regardons le code source de immutableList.get(1000) est un jeu d'enfant.

  get(index, notSetValue) {
    index = wrapIndex(this, index);
    if (index >= 0 && index <pre class="brush:php;toolbar:false">function listNodeFor(list, rawIndex) {
  if (rawIndex >= getTailOffset(list._capacity)) {
    return list._tail;
  }
  if (rawIndex  0) {
      // 循环查找节点所在位置
      node = node.array[(rawIndex >>> level) & MASK];
      level -= SHIFT;
    }
    return node;
  }
}

5. Avantages des arbres à pneus

Voici une photo volée sur Internet :

La structure des données de cet arbre (arbre de pneus) garantit que le nombre de références de copie est réduit au minimum, c'est-à-dire que, grâce à des méthodes extrêmes, le nombre de copies est considérablement réduit. avec 1 million d'attributs Pour un objet, la copie superficielle nécessite 999 999 affectations dans l'arborescence des pneus, en fonction de la profondeur de son accès, un seul niveau ne doit être copié que 31 fois. Ce nombre n'augmente pas avec l'augmentation des attributs de l'objet. Au fur et à mesure que le niveau s'approfondit, le nombre de copies augmentera linéairement. Cependant, comme la profondeur d'accès aux objets ne sera pas particulièrement élevée, le 10ème niveau est presque invisible. Par conséquent, le nombre maximum de copies peut être 300 fois, ce qui est encore très. rapide.

Les situations que j'ai analysées ci-dessus incluent la construction, la modification et la requête. En fait, il existe également des ajouts et des suppressions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!