Immutable.js源碼之List類型是什么-創(chuàng)新互聯(lián)

小編給大家分享一下Immutable.js源碼之List類型是什么，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站建設(shè)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的惠東網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

一、存儲(chǔ)圖解

我以下面這段代碼為例子，畫出這個(gè)List的存儲(chǔ)結(jié)構(gòu)：

let myList = [];
for(let i=0;i<1100;i++) {
    myList[i] = i;
}
debugger;//可以在這里打個(gè)斷點(diǎn)調(diào)試
let immutableList = Immutable.List(myList)
debugger;
console.log(immutableList.set(1000, 'Remm'));
debugger;
console.log(immutableList.get(1000));

二、vector trie 的構(gòu)建過(guò)程

我們用上面的代碼為例子一步一步的解析。首先是把原生的list轉(zhuǎn)換為inmutable的list 類型：

export class List extends IndexedCollection {
  // @pragma Construction

  constructor(value) { // 此時(shí)的value就是上面的myList數(shù)組
    const empty = emptyList();
    if (value === null || value === undefined) {//判斷是否為空
      return empty;
    }
    if (isList(value)) {//判斷是否已經(jīng)是imutable的list類型
      return value;
    }
    const iter = IndexedCollection(value);//序列化數(shù)組
    const size = iter.size;
    if (size === 0) {
      return empty;
    }
    assertNotInfinite(size);
    if (size > 0 && size < SIZE) { // 判斷size是否超過(guò)32
      return makeList(0, size, SHIFT, null, new VNode(iter.toArray()));
    }
    return empty.withMutations(list => {
      list.setSize(size);
      iter.forEach((v, i) => list.set(i, v));
    });
  }

  。。。。。。

}

首先會(huì)創(chuàng)建一個(gè)空的list

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

SHIFT的值為5，export const SHIFT = 5; // Resulted in best performance after ______?

再繼續(xù)看makeList，可以清晰看到 List 的主要部分：

function makeList(origin, capacity, level, root, tail, ownerID, hash) {
  const list = Object.create(ListPrototype);
  list.size = capacity - origin;// 數(shù)組的長(zhǎng)度
  list._origin = origin;// 數(shù)組的起始位置 一般是0
  list._capacity = capacity;// 數(shù)組容量 等于 size
  list._level = level;//樹的深度，為0時(shí)是葉子結(jié)點(diǎn)。默認(rèn)值是5，存儲(chǔ)指數(shù)部分，用于方便位運(yùn)算,增加一個(gè)深度，level值+5
  list._root = root;// trie樹實(shí)現(xiàn)
  list._tail = tail;// 32個(gè)為一組，存放最后剩余的數(shù)據(jù) 其實(shí)就是 %32
  list.__ownerID = ownerID;
  list.__hash = hash;
  list.__altered = false;
  return list;
}

將傳入的數(shù)據(jù)序列化

// ArraySeq
iter = {
size: 數(shù)組的length,
_array: 傳入數(shù)組的引用
}

判斷size是否超過(guò)32，size > 0 && size < SIZE 這里 SIZE ： export const SIZE = 1 << SHIFT;即 32。若沒(méi)有超過(guò)32，所有數(shù)據(jù)都放在_tail中。

_root 和 _tail 里面的數(shù)據(jù)又有以下結(jié)構(gòu)：

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

可以這樣調(diào)試查看：

let myList = [];
for(let i=0;i<30;i++) {
    myList[i] = i;
}
debugger;//可以在這里打個(gè)斷點(diǎn)調(diào)試
console.log(Immutable.List(myList));

size如果超過(guò)32

return empty.withMutations(list => {
    list.setSize(size);//構(gòu)建樹的結(jié)構(gòu) 主要是計(jì)算出樹的深度
    iter.forEach((v, i) => list.set(i, v));//填充好數(shù)據(jù)
});

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

list.setSize(size)中有一個(gè)重要的方法setListBounds,下面我們主要看這個(gè)方法如何構(gòu)建這顆樹

這個(gè)方法最主要的作用是 確定 list的level

function setListBounds(list, begin, end) {

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

  // New size might need creating a higher root.
  // 是否需要增加數(shù)的深度 把 1 左移 newLevel + SHIFT 位 相當(dāng)于 1 * 2 ^ (newLevel + SHIFT)
  // 以 size為 1100 為例子 newTailOffset的值為1088 第一次 1088 > 2 ^ 10 樹增加一層深度
  // 第二次 1088 < 2 ^ 15 跳出循環(huán) newLevel = 10
 while (newTailOffset >= 1 << (newLevel + SHIFT)) {
    newRoot = new VNode(
      newRoot && newRoot.array.length ? [newRoot] : [],
      owner
    );
    newLevel += SHIFT;
  }

  ......
}

function getTailOffset(size) {
    // (1100 - 1) / 2^5 % 2^5 = 1088
    return size < SIZE ? 0 : (((size - 1) >>> SHIFT) << SHIFT);
}

經(jīng)過(guò) list.setSize(size);構(gòu)建好的結(jié)構(gòu)

三、set 方法

listiter.forEach((v, i) => list.set(i, v));這里是將iter中的_array填充到

這里主要還是看看set方法如何設(shè)置數(shù)據(jù)

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) {
  // 根據(jù) index 和 level 計(jì)算 數(shù)據(jù)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節(jié)點(diǎn)的array復(fù)制一份生成一個(gè)新的節(jié)點(diǎn)newNode editableVNode函數(shù)見下面源碼
    newNode = editableVNode(node, ownerID);
    // 回溯階段將 子節(jié)點(diǎn)的引用賦值給自己
    newNode.array[idx] = newLowerNode;
    return newNode;
  }
  ......
  newNode = editableVNode(node, ownerID);
  // 當(dāng)遞歸到葉子節(jié)點(diǎn) 也就是level <= 0 將值放到這個(gè)位置
  newNode.array[idx] = value;
  ......
  return newNode;
}

function editableVNode(node, ownerID) {
  if (ownerID && node && ownerID === node.ownerID) {
    return node;
  }
  return new VNode(node ? node.array.slice() : [], ownerID);
}

下面我們看看運(yùn)行了一次set(0,0)的結(jié)果

整個(gè)結(jié)構(gòu)構(gòu)建完之后

下面我們接著看剛剛我們構(gòu)建的list set(1000, 'Remm'),其實(shí)所有的set的源碼上面已經(jīng)解析過(guò)了，我們?cè)賮?lái)溫習(xí)一下。

調(diào)用上面的set方法，index=1000,value='Remm'。調(diào)用updateList，繼而調(diào)用updateVNode。通過(guò)const idx = (index >>> level) & MASK;計(jì)算要尋找的節(jié)點(diǎn)的位置(在這個(gè)例子中，idx的值依次是0->31->8)。 不斷的遞歸查找，當(dāng) level <= 0 到達(dá)遞歸的終止條件，其實(shí)就是達(dá)到樹的葉子節(jié)點(diǎn)，此時(shí)通過(guò)newNode = editableVNode(node, ownerID);創(chuàng)建一個(gè)新的節(jié)點(diǎn)，然后 newNode.array[8] = 'Remm'。接著就是開始回溯，在回溯階段，自己把自己克隆一個(gè)，newNode = editableVNode(node, ownerID);,注意這里克隆的只是引用，所以不是深拷貝。然后再將idx位置的更新了的子節(jié)點(diǎn)重新賦值，newNode.array[idx] = newLowerNode;,這樣沿著路徑一直返回，更新路徑上的每個(gè)節(jié)點(diǎn)，最后得到一個(gè)新的根節(jié)點(diǎn)。

更新后的list:

四、get 方法

了解完上面的list構(gòu)建和set，我們?cè)賮?lái)看 immutableList.get(1000) 源碼就是小菜一碟了。

  get(index, notSetValue) {
    index = wrapIndex(this, index);
    if (index >= 0 && index < this.size) {
      index += this._origin;
      const node = listNodeFor(this, index);
      return node && node.array[index & MASK];
    }
    return notSetValue;
  }

function listNodeFor(list, rawIndex) {
  if (rawIndex >= getTailOffset(list._capacity)) {
    return list._tail;
  }
  if (rawIndex < 1 << (list._level + SHIFT)) {
    let node = list._root;
    let level = list._level;
   while (node && level > 0) {
      // 循環(huán)查找節(jié)點(diǎn)所在位置
      node = node.array[(rawIndex >>> level) & MASK];
      level -= SHIFT;
    }
    return node;
  }
}

五、tire 樹 的優(yōu)點(diǎn)

來(lái)一張從網(wǎng)上盜來(lái)的圖：

這種樹的數(shù)據(jù)結(jié)構(gòu)（tire 樹），保證其拷貝引用的次數(shù)降到了最低，就是通過(guò)極端的方式，大大降低拷貝數(shù)量，一個(gè)擁有100萬(wàn)條屬性的對(duì)象，淺拷貝需要賦值 99.9999萬(wàn)次，而在 tire 樹中，根據(jù)其訪問(wèn)的深度，只有一個(gè)層級(jí)只需要拷貝 31 次，這個(gè)數(shù)字不隨著對(duì)象屬性的增加而增大。而隨著層級(jí)的深入，會(huì)線性增加拷貝數(shù)量，但由于對(duì)象訪問(wèn)深度不會(huì)特別高，10 層已經(jīng)幾乎見不到了，因此最多拷貝300次，速度還是非?？斓摹?/p>

我上面所解析的情況有 構(gòu)建、修改、查詢。其實(shí)還有 添加 和 刪除。

看完了這篇文章，相信你對(duì)Immutable.js源碼之List類型是什么有了一定的了解，想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章題目：Immutable.js源碼之List類型是什么-創(chuàng)新互聯(lián)
本文來(lái)源：http://muchs.cn/article22/csjgjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、搜索引擎優(yōu)化、網(wǎng)站策劃、服務(wù)器托管、品牌網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)