Detaillierte Analyse des Listentyps des Immutable.js-Quellcodes (mit Beispielen)

Dieser Artikel bietet Ihnen eine detaillierte Analyse des List-Typs des Immutable.js-Quellcodes (mit Beispielen). Ich hoffe, er wird Ihnen als Referenz dienen.

1. Speicherdiagramm

Ich verwende den folgenden Code als Beispiel, um die Speicherstruktur dieser Liste zu zeichnen:

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="Detaillierte Analyse des Listentyps des Immutable.js-Quellcodes (mit Beispielen)"></span></p><p><strong>2. Der Konstruktionsprozess des Vektorversuchs</strong></p><p>Wir verwenden den obigen Code als Beispiel, um ihn Schritt für Schritt zu analysieren. Der erste Schritt besteht darin, die native Liste in einen unveränderlichen Listentyp umzuwandeln: </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));
    });
  }

  。。。。。。

}

Zuerst wird eine leere Liste erstellt

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

Der Wert von SHIFT ist 5, export const SHIFT = 5; // Erzielte die beste Leistung nach ______?

Schauen Sie sich weiterhin makeList an, und Sie können die Hauptteile der Liste deutlich erkennen:

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;
}

Eingehende Daten serialisieren

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

Beurteilen Sie, ob die Größe 32 überschreitet, Größe

_root und _tail haben die folgende Struktur:

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

können wie folgt debuggt und angezeigt werden:

let myList = [];
for(let i=0;i<p>Größe, wenn sie 32 überschreitet</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;
}

Liste. Es gibt eine wichtige Methode setListBounds in setSize(size). Im Folgenden werden wir uns hauptsächlich ansehen, wie diese Methode diesen Baum erstellt

Die Hauptfunktion dieser Methode besteht darin, die Ebene der Liste zu bestimmen

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> durch die Liste.</p><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Detaillierte Analyse des Listentyps des Immutable.js-Quellcodes (mit Beispielen)"></span></p><p><strong>3 </strong>listiter.forEach( (v, i) => list.set(i, v));Hier geht es darum, das _array im Iter zu füllen </p><p>Hier geht es vor allem darum, zu sehen, wie die Menge aussieht Methode legt die Daten fest</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);
}

Werfen wir einen Blick auf die Ergebnisse der einmaligen Ausführung

set(0,0)

Nachdem die gesamte Struktur fertig ist gebaut

Schauen wir uns den Listensatz (1000, 'Remm') an, den wir gerade erstellt haben. Tatsächlich wurde der Quellcode aller Sätze erstellt Sehen wir uns das noch einmal an.

Rufen Sie die obige Set-Methode auf, Index=1000, Wert='Remm'. Rufen Sie updateList und dann updateVNode auf. Berechnen Sie die Position des gesuchten Knotens durch const idx = (index >>> level) & MASK; (in diesem Beispiel sind die Werte von idx 0->31->8). Kontinuierliche rekursive Suche: Wenn Level

Aktualisierte Liste:

4. Methode abrufen

Die obige Liste verstanden Aufbau und Satz, schauen wir uns den Quellcode von immutableList.get(1000) an, ist ein Kinderspiel.

  get(index, notSetValue) {
    index = wrapIndex(this, index);
    if (index >= 0 && index rrree<p></p>5. Vorteile von Reifenbäumen<p><strong></strong>Hier ist ein aus dem Internet geklautes Bild: </p><p></p><p><img src="https://img.php.cn//upload/image/637/806/843/1543214787610725.png" title="1543214787610725.png" alt="Detaillierte Analyse des Listentyps des Immutable.js-Quellcodes (mit Beispielen)"> <span class="img-wrap"></span>Die Datenstruktur dieses Baums (Reifenbaum) stellt sicher, dass die Anzahl der Kopienreferenzen auf ein Minimum reduziert wird, d. h. durch extreme Methoden wird die Anzahl der Kopien stark reduziert. Für ein Objekt mit 1 Million Attributen , flaches Kopieren ist erforderlich Die Zuweisung beträgt 999.999 Mal. Im Reifenbaum muss je nach Zugriffstiefe nur 31 Mal kopiert werden. Diese Zahl erhöht sich nicht, wenn die Objektattribute zunehmen. Mit zunehmender Tiefe nimmt die Anzahl der Kopien linear zu. Da die Objektzugriffstiefe jedoch nicht besonders hoch ist, ist die 10. Ebene nahezu unsichtbar. Daher kann die maximale Anzahl der Kopien immer noch sehr hoch sein schnell. </p><p>Zu den Situationen, die ich oben analysiert habe, gehören Konstruktion, Änderung und Abfrage. Tatsächlich gibt es auch Hinzufügen und Löschen. </p>

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse des Listentyps des Immutable.js-Quellcodes (mit Beispielen). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!