Immutable.js ソース コードの List 型の詳細な分析 (例付き)

この記事では、Immutable.js のソース コードの List タイプの詳細な分析を紹介します (サンプル付き)。必要な方は参考にしていただければ幸いです。

1. ストレージ図

このリストのストレージ構造を描画するために、例として次のコードを使用します。

##2. ベクトル トライの構築プロセス

上記のコードを例として使用し、段階的に分析します。 1 つ目は、ネイティブ リストを不変リスト型に変換することです。

let myList = [];
for(let i=0;i最初に、空のリストが作成されます<p></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));
    });
  }

  。。。。。。

}

SHIFT の値は 5、export const SHIFT = 5; / ______ 後に最高のパフォーマンスが得られました?

引き続き makeList を確認すると、リストの主要部分がはっきりとわかります:

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

受信データのシリアル化

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

Determineサイズが 32 を超えるかどうかは、size > 0 && size _root と _tail のデータは次の構造になっています:

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

次のようにデバッグして表示できます:

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

size (32

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

# を超える場合) ##list。setSize(size) には重要なメソッド setListBounds があります。以下では、このメソッドがどのようにこのツリーを構築するかを主に説明します。

このメソッドの主な機能は、リストのレベルを決定することです

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

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 <p>setSize(size);構築された構造</p><p></p><p></p><p>##3. <span class="img-wrap">##listiter.forEach( (v, i) => list.set(i, v));ここでは iter の _array を <img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Immutable.js ソース コードの List 型の詳細な分析 (例付き)"></span> に設定します。ここで重要なことは、その方法を確認することです。 set メソッドはデータを設定します</p><pre class="brush:php;toolbar:false">function getTailOffset(size) {
    // (1100 - 1) / 2^5 % 2^5 = 1088
    return size >> SHIFT) <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 <p>set(0,0)<strong></strong></p><p></p><p> の実行結果を見てみましょう</p>#全体の構造が構築された後<p><code></code></p><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/917/198/991/1543214730741059.png" title="1543214730741059.png" alt="Immutable.js ソース コードの List 型の詳細な分析 (例付き)">構築したばかりのリスト セット (1000、'Remm') を見てみましょう。実際、すべてのセットのソース コードは上記で解析されています。もう一度確認してみましょう。 </span></p>上記の set メソッドを呼び出します (index=1000、value='Remm')。 updateList を呼び出してから、updateVNode を呼び出します。 const idx = (index >>> level) & MASK; で探しているノードの位置を計算します（この例では、idx の値は 0->31->8 です）。継続的な再帰検索では、レベル 更新されたリスト:<p><span class="img-wrap"><img src="https://img.php.cn//upload/image/528/784/609/1543214743968157.png" title="1543214743968157.png" alt="Immutable.js ソース コードの List 型の詳細な分析 (例付き)"></span></p><p></p><p>4. 取得方法</p><p></p>上記を完全に理解するimmutableList.get(1000) のソースコードを見てみましょう。リストの構築と設定は簡単です。 <p></p><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);
}

  get(index, notSetValue) {
    index = wrapIndex(this, index);
    if (index >= 0 && index <span class="img-wrap"><img src="https://img.php.cn//upload/image/580/763/873/1543214755484770.png" title="1543214755484770.png" alt="Immutable.js ソース コードの List 型の詳細な分析 (例付き)">5. Tire Tree の利点</span><p> これはインターネットから盗まれた写真です: <strong></strong></p><p></p> <p><strong>このツリー (タイヤ ツリー) のデータ構造により、コピー参照の数が最小限に抑えられます。つまり、100 万個の属性を持つオブジェクトのコピー数が大幅に削減されます。 、浅いコピーが必要です。タイヤ ツリーでは、アクセスの深さに応じて 999,999 回コピーする必要があります。この数は、オブジェクトの属性が増加しても増加しません。レベルが深くなるにつれてコピー数は直線的に増加しますが、オブジェクトのアクセス深度はそれほど高くないため、10 レベルではコピーの最大数は 300 回であり、それでも非常に高速です。 。 </strong></p>上で分析した状況には、構築、変更、クエリが含まれます。実際には、追加と削除もあります。 <p></p>

以上がImmutable.js ソース コードの List 型の詳細な分析 (例付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。