Immutable.js 소스 코드의 List 유형에 대한 자세한 분석(예제 포함)

이 기사는 Immutable.js 소스 코드의 자세한 분석을 제공합니다(예제 포함). 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

1. 저장 다이어그램

이 목록의 저장 구조를 그리기 위해 다음 코드를 예로 사용합니다.# 🎜🎜#

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="Immutable.js 소스 코드의 List 유형에 대한 자세한 분석(예제 포함)"></span></p><p> 2. 벡터 트라이의 구축 과정<strong></strong>#🎜 🎜 #위 코드를 예로 들어 단계별로 분석해보겠습니다. 첫 번째 단계는 기본 목록을 변경할 수 없는 목록 유형으로 변환하는 것입니다. </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));
    });
  }

  。。。。。。

}

먼저 빈 목록이 생성됩니다

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

SHIFT 값은 5이고 const를 내보냅니다. SHIFT = 5; // ______ 이후 최고의 성능을 얻었습니까?

makeList를 계속 살펴보면 목록의 주요 부분을 명확하게 볼 수 있습니다.

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

들어오는 항목을 직렬화합니다. data#🎜🎜 #

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

크기가 32를 초과하는지 확인합니다. size > 0 && SIZE 여기에서는 SIZE: import const SIZE = 1 _root 및 _tail의 데이터는 다음과 같은 구조를 갖습니다.

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

디버깅하고 다음과 같이 볼 수 있습니다.

let myList = [];
for(let i=0;isize를 초과하는 경우 32#🎜🎜 #<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;
}

list.setSize(size)에는 setListBounds라는 중요한 메소드가 있습니다. 아래에서는 이 메소드가 이 트리를 구축하는 방법을 주로 살펴봅니다.

이 메소드의 주요 기능은 다음과 같습니다. 목록의 수준을 결정하기 위해

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 rrree<p>list.setSize(size); 🎜🎜#3. set method</p><p></p>listiter.forEach( (v, i) => list.set(i, v)); 이것은 iter의 _array를 채우는 것입니다. <p></p>여기에서 가장 중요한 것은 set 메소드가 데이터를 설정하는 방법을 확인하는 것입니다. <p></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 <span class="img-wrap">실행 결과를 살펴보겠습니다 <img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Immutable.js 소스 코드의 List 유형에 대한 자세한 분석(예제 포함)"> 한번</span># 🎜🎜#<p><strong></strong>#🎜 🎜 #전체구조가 완성된 후</p><p></p><p></p><p>#🎜 🎜# 리스트 세트(1000, 'Remm')를 살펴보겠습니다. 실제로 위에서 모든 세트의 소스 코드가 분석되었습니다. <code>set(0,0)</code></p>위의 set 메소드를 호출합니다. index=1000, value='Remm'. updateList를 호출한 다음 updateVNode를 호출합니다. 찾고 있는 노드의 위치를 ​​const idx = (index>>> level) & MASK; (이 예에서 idx 값은 0->31->8)로 계산합니다. 연속 재귀 검색, 레벨 <span class="img-wrap">업데이트된 목록:<img src="https://img.php.cn//upload/image/917/198/991/1543214730741059.png" title="1543214730741059.png" alt="Immutable.js 소스 코드의 List 유형에 대한 자세한 분석(예제 포함)"></span><p></p><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 유형에 대한 자세한 분석(예제 포함)">4. #</span></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);
}

rrree

5. 타이어트리의 장점

인터넷에서 훔친 사진입니다:

# 🎜 🎜#

이 트리(타이어 트리)의 데이터 구조는 복사 참조 수를 최소한으로 줄이는 것을 보장합니다. 즉, 극단적인 방법을 통해 복사본 수가 크게 줄어들면, 100만 개의 속성을 가진 객체는 얕은 복사를 위해 999,999번 할당되어야 합니다. 타이어 트리에서는 액세스 깊이에 따라 한 수준만 31번만 복사하면 됩니다. 개체 속성이 증가하면 증가합니다. 레벨이 깊어질수록 복사 횟수는 선형적으로 증가하지만, 객체 접근 깊이가 특별히 높지 않기 때문에 10레벨은 거의 눈에 띄지 않습니다. 따라서 최대 복사 횟수는 여전히 매우 빠릅니다. . 위에서 분석한 상황에는 구축, 수정, 쿼리가 포함됩니다. 실제로 추가 및 삭제도 있습니다.

위 내용은 Immutable.js 소스 코드의 List 유형에 대한 자세한 분석(예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!