资讯专栏INFORMATION COLUMN

Immutable.js 源码解析 --List 类型

Doyle / 2518人阅读

摘要:首先是把原生的转换为的类型此时的就是上面的数组判断是否为空判断是否已经是的类型序列化数组判断是否超过。。。。。。若没有超过,所有数据都放在中。通过计算要寻找的节点的位置在这个例子中,的值依次是。我上面所解析的情况有构建修改查询。

一、存储图解

我以下面这段代码为例子,画出这个List的存储结构:

</>复制代码

  1. let myList = [];
  2. for(let i=0;i<1100;i++) {
  3. myList[i] = i;
  4. }
  5. debugger;//可以在这里打个断点调试
  6. let immutableList = Immutable.List(myList)
  7. debugger;
  8. console.log(immutableList.set(1000, "Remm"));
  9. debugger;
  10. console.log(immutableList.get(1000));

二、vector trie 的构建过程

我们用上面的代码为例子一步一步的解析。首先是把原生的list转换为inmutable的list 类型:

</>复制代码

  1. export class List extends IndexedCollection {
  2. // @pragma Construction
  3. constructor(value) { // 此时的value就是上面的myList数组
  4. const empty = emptyList();
  5. if (value === null || value === undefined) {//判断是否为空
  6. return empty;
  7. }
  8. if (isList(value)) {//判断是否已经是imutable的list类型
  9. return value;
  10. }
  11. const iter = IndexedCollection(value);//序列化数组
  12. const size = iter.size;
  13. if (size === 0) {
  14. return empty;
  15. }
  16. assertNotInfinite(size);
  17. if (size > 0 && size < SIZE) { // 判断size是否超过32
  18. return makeList(0, size, SHIFT, null, new VNode(iter.toArray()));
  19. }
  20. return empty.withMutations(list => {
  21. list.setSize(size);
  22. iter.forEach((v, i) => list.set(i, v));
  23. });
  24. }
  25. 。。。。。。
  26. }

首先会创建一个空的list

</>复制代码

  1. let EMPTY_LIST;
  2. export function emptyList() {
  3. return EMPTY_LIST || (EMPTY_LIST = makeList(0, 0, SHIFT));
  4. }

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

再继续看makeList,可以清晰看到 List 的主要部分:

</>复制代码

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

将传入的数据序列化

</>复制代码

  1. // ArraySeq
  2. iter = {
  3. size: 数组的length,
  4. _array: 传入数组的引用
  5. }

判断size是否超过32,size > 0 && size < SIZE 这里 SIZE : export const SIZE = 1 << SHIFT;
即 32。若没有超过32,所有数据都放在_tail中。

_root 和 _tail 里面的数据又有以下结构:

</>复制代码

  1. // @VNode class
  2. constructor(array, ownerID) {
  3. this.array = array;
  4. this.ownerID = ownerID;
  5. }

可以这样调试查看:

</>复制代码

  1. let myList = [];
  2. for(let i=0;i<30;i++) {
  3. myList[i] = i;
  4. }
  5. debugger;//可以在这里打个断点调试
  6. console.log(Immutable.List(myList));

size如果超过32

</>复制代码

  1. return empty.withMutations(list => {
  2. list.setSize(size);//构建树的结构 主要是计算出树的深度
  3. iter.forEach((v, i) => list.set(i, v));//填充好数据
  4. });

</>复制代码

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

list.setSize(size)中有一个重要的方法setListBounds,下面我们主要看这个方法如何构建这颗树
这个方法最主要的作用是 确定 list的level

</>复制代码

  1. function setListBounds(list, begin, end) {
  2. ......
  3. const newTailOffset = getTailOffset(newCapacity);
  4. // New size might need creating a higher root.
  5. // 是否需要增加数的深度 把 1 左移 newLevel + SHIFT 位 相当于 1 * 2 ^ (newLevel + SHIFT)
  6. // 以 size为 1100 为例子 newTailOffset的值为1088 第一次 1088 > 2 ^ 10 树增加一层深度
  7. // 第二次 1088 < 2 ^ 15 跳出循环 newLevel = 10
  8. while (newTailOffset >= 1 << (newLevel + SHIFT)) {
  9. newRoot = new VNode(
  10. newRoot && newRoot.array.length ? [newRoot] : [],
  11. owner
  12. );
  13. newLevel += SHIFT;
  14. }
  15. ......
  16. }

</>复制代码

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

经过 list.setSize(size);构建好的结构

三、set 方法

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

这里主要还是看看set方法如何设置数据

</>复制代码

  1. set(index, value) {
  2. return updateList(this, index, value);
  3. }

</>复制代码

  1. function updateList(list, index, value) {
  2. ......
  3. if (index >= getTailOffset(list._capacity)) {
  4. newTail = updateVNode(newTail, list.__ownerID, 0, index, value, didAlter);
  5. } else {
  6. newRoot = updateVNode(
  7. newRoot,
  8. list.__ownerID,
  9. list._level,
  10. index,
  11. value,
  12. didAlter
  13. );
  14. }
  15. ......
  16. }

</>复制代码

  1. function updateVNode(node, ownerID, level, index, value, didAlter) {
  2. // 根据 index 和 level 计算 数据set的位置在哪
  3. const idx = (index >>> level) & MASK;
  4. // 利用递归 一步一步的寻找位置 直到找到最终的位置
  5. if (level > 0) {
  6. const lowerNode = node && node.array[idx];
  7. const newLowerNode = updateVNode(
  8. lowerNode,
  9. ownerID,
  10. level - SHIFT,
  11. index,
  12. value,
  13. didAlter
  14. );
  15. ......
  16. // 把node节点的array复制一份生成一个新的节点newNode editableVNode函数见下面源码
  17. newNode = editableVNode(node, ownerID);
  18. // 回溯阶段将 子节点的引用赋值给自己
  19. newNode.array[idx] = newLowerNode;
  20. return newNode;
  21. }
  22. ......
  23. newNode = editableVNode(node, ownerID);
  24. // 当递归到叶子节点 也就是level <= 0 将值放到这个位置
  25. newNode.array[idx] = value;
  26. ......
  27. return newNode;
  28. }

</>复制代码

  1. function editableVNode(node, ownerID) {
  2. if (ownerID && node && ownerID === node.ownerID) {
  3. return node;
  4. }
  5. return new VNode(node ? node.array.slice() : [], ownerID);
  6. }

下面我们看看运行了一次set(0,0)的结果

整个结构构建完之后

下面我们接着看刚刚我们构建的list set(1000, "Remm"),其实所有的set的源码上面已经解析过了,我们再来温习一下。

调用上面的set方法,index=1000,value="Remm"。调用updateList,继而调用updateVNode。通过const idx = (index >>> level) & MASK;计算要寻找的节点的位置(在这个例子中,idx的值依次是0->31->8)。 不断的递归查找,当 level <= 0 到达递归的终止条件,其实就是达到树的叶子节点,此时通过newNode = editableVNode(node, ownerID);创建一个新的节点,然后 newNode.array[8] = "Remm"。接着就是开始回溯,在回溯阶段,自己把自己克隆一个,newNode = editableVNode(node, ownerID);,注意这里克隆的只是引用,所以不是深拷贝。然后再将idx位置的更新了的子节点重新赋值,newNode.array[idx] = newLowerNode;,这样沿着路径一直返回,更新路径上的每个节点,最后得到一个新的根节点。

更新后的list:

四、get 方法

了解完上面的list构建和set,我们再来看 immutableList.get(1000) 源码就是小菜一碟了。

</>复制代码

  1. get(index, notSetValue) {
  2. index = wrapIndex(this, index);
  3. if (index >= 0 && index < this.size) {
  4. index += this._origin;
  5. const node = listNodeFor(this, index);
  6. return node && node.array[index & MASK];
  7. }
  8. return notSetValue;
  9. }

</>复制代码

  1. function listNodeFor(list, rawIndex) {
  2. if (rawIndex >= getTailOffset(list._capacity)) {
  3. return list._tail;
  4. }
  5. if (rawIndex < 1 << (list._level + SHIFT)) {
  6. let node = list._root;
  7. let level = list._level;
  8. while (node && level > 0) {
  9. // 循环查找节点所在位置
  10. node = node.array[(rawIndex >>> level) & MASK];
  11. level -= SHIFT;
  12. }
  13. return node;
  14. }
  15. }
五、tire 树 的优点

来一张从网上盗来的图:

这种树的数据结构(tire 树),保证其拷贝引用的次数降到了最低,就是通过极端的方式,大大降低拷贝数量,一个拥有100万条属性的对象,浅拷贝需要赋值 99.9999万次,而在 tire 树中,根据其访问的深度,只有一个层级只需要拷贝 31 次,这个数字不随着对象属性的增加而增大。而随着层级的深入,会线性增加拷贝数量,但由于对象访问深度不会特别高,10 层已经几乎见不到了,因此最多拷贝300次,速度还是非常快的。

我上面所解析的情况有 构建、修改、查询。其实还有 添加 和 删除。
其实Immutable.js 部分参考了 Clojure 中的PersistentVector的实现方式。所以可以看看下面这篇文章:

https://hypirion.com/musings/...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/99338.html

相关文章

  • Immutable.js 源码解析 --Map 类型

    摘要:那对于结构又要如何处理,没有结构的索引,那怎么办呢我们把键名变为哈希值就可以啦。表示存在,表示不存在。例如转换为二进制后为每位为一组,假定为取出需要的位。类对应带的,代表其子元素的数量。 上一片文章介绍的是 List 结构。那对于 Map 结构又要如何处理,没有 List 结构的索引,那怎么办呢? 我们把键名变为哈希值就可以啦~ HAMT:Hash Arrey Mapped Trie ...

    Alliot 评论0 收藏0
  • Immutable.js 初识

    摘要:文章博客地址所创建的数据有一个迷人的特性数据创建后不会被改变。是的基类,使用该类时需要至少继承其子类中的一个。总结所提供的和固有的各有优势,未来有可能制定一套原生的规范,在这之前,是一个不错的选择。参考资料官方文档 文章博客地址:http://pinggod.com/2016/Immutable/ Immutable.js 所创建的数据有一个迷人的特性:数据创建后不会被改变。我们使用 ...

    Olivia 评论0 收藏0
  • ImmutableJS

    摘要:持久化数据提供可修改的,这些不在原地更新数据,而是产生新的更新后的数据。提供了很多持久化不可变数据结构,包括以及。也提供了惰性允许有效的方法链式操作,例如和,不用创建中介变量。 简介  JavaScript中的不可变集合 不可变数据一旦创建就不能改变,这样可简化应用开发、无防御复制、启用更先进的内存方案,以及使用更简单的逻辑检查更新。持久化数据提供可修改的API,这些API不在原地更新...

    沈俭 评论0 收藏0
  • 前端数据扁平化与持久化

    摘要:与持久化工程师花了年时间打造,与同期出现。有持久化数据结构,如等,并发安全。总结篇幅有限,时间也比较晚了,关于前端数据的扁平化与持久化处理先讲这么多了,有兴趣的同学可以关注下,后面有时间会多整理分享。 (PS: 时间就像海绵里的水,挤到没法挤,只能挤挤睡眠时间了~ 知识点还是需要整理的,付出总会有收获,tired but fulfilled~) 前言 最近业务开发,从零搭建网页生成器,...

    dreamtecher 评论0 收藏0
  • 初学immutable.js的一些总结

    摘要:在中,的返回值是,即一个新的对象。该方法在中的和中均有使用,但是此处的方法返回的是一个布尔值。是排序方法,可以传入一个函数,通过返回值的正负确定元素的前后排序顺序。 1.immutableObj在复制的时候,复制的是引用。 === 比较的是引用是否一样。而is()和equal()表示的是值是否一样,什么是值,我认为就是将一个对象Json.stringify()之后的的数据。 总体而言,...

    Near_Li 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<