FE / 算法
16 minutes read (About 2336 words)

React, Vue2, Vue3 diff 算法解析

前言

前端的虚拟 DOM 框架，一般是用 js 树结构来对视图层进行抽象表达，通过对树的遍历创建 UI 元素，渲染到视图。
如果想要对视图进行更新，这时候会产生一颗新的树，显然根据新的数据全量重新创建 UI 元素，渲染到视图是极其消耗性能的。
因此需要对新老两颗树进行对比，找到差异点，将差异部分更新到存在的视图。

为了保证性能，我们需要考虑以下下几点:

  1. 尽可能复用现有 UI 元素
  2. 减少对 UI 元素的操作
  3. 减少遍历次数

在实际场景中，其实基本不会遇到子树的层级跃迁移动，往往只会对同一层级的元素进行更新。所以没必要进行跨层级的比较。于是就变成了两个数组之间的比较。

正文

基于以上可以抽象为一道算法题：
存在 oldChildren newChildren 两个数组，数组元素在该数组内都是唯一且不重复的，UIChildren 初始值为 oldChildren 的副本，

  1. 尽可能少地操作读取 UIChildren
  2. 尽可能少地读写 oldChildren 和 newChildren
  3. 优先满足第一点

尽可能利用 UIChildren 中的现有元素（newChildren，oldChildren 中的交集元素在 UIChildren 中 只能被移动不能被删除），
通过对比 oldChildren 和 newChildren 实现将 UIChildren 变为 newChildren 的副本
例如；
oldChildren 为 [1, 3, 4]
newChildren 为 [1, 2, 4]
那么 UIChildren 的初始值为 [1, 3, 4]
最后返回的 UIChildren 为 [1, 2, 4]
值得注意的是，对 UIChildren 进行操作的过程中，1 和 4 是属于可以复用的元素，所以只可以被移动但是不可以被删除的元素。

1
2
3
4
5
function diff(oldChildren, newChildren) {
  let UIChildren = oldChildren.map(v => v) // clone
  // TODO:
  return UIChildren
}

对 UIChildren 进行操作提供了以下几个 API（其实是为了模拟 DOM 的 API，它和数组用法上设计风格差异很大，一个基于 index，一个基于元素）

  • inesertBefore(UIChildren, child, refChild) 讲一个元素插入到某一个元素前面
  • removeChild(UIChildren, child) 移除某一个元素
  • nextSibling(UIChildren, child) 获取某一个元素之后的元素
    具体实现参见

React

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * @desc React diff 算法
 * 核心思想：进行双层循环, 一旦遇到相同的节点, 
 * 与上次记录的 oldChildren 中的最大 index 进行比较，
 * 如果本次 index >  lastIndex 则说明顺序新旧一致，无需移动，只需记录本次 index 到 lastIndex
 * 否则说明需要将本节点移动到上一个节点之后
 * 由于始终使用后移的方式来调整顺序，
 * 这种场景下 [1, 2, 3, ..., 100] -> [100, 1, 2, ..., 99]，需要将 1-99 向后移动，共计需要99次操作。
 * 而不是将 100 插入到 1 前面，这样只需一次操作
 * 操作指使用提供的 DOM API
 * @param {[number]} oldChildren 
 * @param {[number]} newChildren 
 */
export function diff(oldChildren, newChildren) {
  let UIChildren = oldChildren.map(v => v);
  let lastIndex = 0;

  if (newChildren.length === 0) {
    UIChildren = []
  }
  
  for (let n = 0; n < newChildren.length; n++) {
    const newNode = newChildren[n]
    // 暂存上一个节点的的最大 index, 
    // 如果后续节点相同且 index < lastIndex, 则说明该节点需要向后移动
    let hasFind = false; // 是否找到元素
    let o = 0; 
    for(o; o < oldChildren.length; o++) {
      const oldNode = oldChildren[o]
      if (newNode === oldNode) {
        hasFind = true
        if (o < lastIndex) {
          // 当前节点和 n-1 节点顺序错位, 需要将当前节点插入到 n-1 后一位（的前面）, 
          const refNode = nextSibling(UIChildren, newChildren[n - 1])
          inesertBefore(UIChildren, oldNode, refNode)
        } else {
          lastIndex = o
        }
        // 一旦有节点相同, 中断内层循环, 防止继续更新下去浪费性能
        break
      }
    }

    // oldChildren 里面找不到 newChildren 的元素 说明要新增
    // i 为 0 ,说明遍历的是第一个元素, 插入到 UIChildren 的第一个节点即可
    // i >= 1, 直接插入到该元素前面
    if (!hasFind) {
      const refNode = n - 1 < 0 ? oldChildren[0] : nextSibling(UIChildren, newChildren[n - 1])
      inesertBefore(UIChildren, newChildren[n], refNode)
    }

    // newChildren 里面找不到 oldChildren 里面的元素说明要移除
    for (let i = 0; i < oldChildren.length; i++) {
      const item = oldChildren[i];
      const hasFind = newChildren.find(v => v === item)
      if (!hasFind) {
        removeChild(UIChildren, item)
      }
    }
  }
  return UIChildren
}

代码参见

Snabddom / Vue2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * @desc snabbdom & vue2 中采用的双端比较算法
 * 一层循环同时遍历两个数组, 通过组合 oldStart, oldEnd 和 newStart，newEnd 进行双端比较
 * 一共会有四种情况，直到某一个数组遍历完成
 * 然后处理未遍历到的区间
 * @param {[number]} oldChildren 
 * @param {[number]} newChildren 
 */
export function diff(oldChildren, newChildren) {
  let UIChildren = oldChildren.map(v => v) // 模拟 UI 元素
  let oldStartIdx = 0
  let newStartIdx = 0

  let oldEndIdx = oldChildren.length - 1
  let newEndIdx = newChildren.length - 1

  let oldStartNode = oldChildren[0]
  let newStartNode = newChildren[0]

  let oldEndNode = oldChildren[oldEndIdx]
  let newEndNode = newChildren[newEndIdx]

  while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (!oldStartNode) {
      oldStartNode = oldChildren[++oldStartIdx]
    } else if(!oldEndNode) {
      oldEndNode = oldChildren[--oldEndIdx]
    } else  if (oldStartNode === newStartNode) {
      oldStartNode = oldChildren[++oldStartIdx]
      newStartNode = newChildren[++newStartIdx]
    } else if (oldEndNode === newEndNode) {
      oldEndNode = oldChildren[--oldEndIdx]
      newEndNode = newChildren[--newEndIdx]
    } else if (oldStartNode === newEndNode) {
      // 后移
      // 将节点移动到剩余遍历区域最后一个节点之后
      inesertBefore(UIChildren, oldStartNode, nextSibling(UIChildren, oldEndNode))
      oldStartNode = oldChildren[++oldStartIdx]
      newEndNode = newChildren[--newEndIdx]
    } else if (oldEndNode === newStartNode) {
      // 前移
      // 将节点移动到遍历区域最第一个节点之前
      inesertBefore(UIChildren, oldEndNode, oldStartNode)
      oldEndNode = oldChildren[--oldEndIdx]
      newStartNode = newChildren[++newStartIdx]
    } else {
      // 其他情况
      // 拿 newChildren 中的起始节点尝试去 oldChildren 中寻找
      const newEle = newChildren[newStartIdx]
      const oldIdx = oldChildren.indexOf(newEle)
      if (oldIdx === -1) {
        // 找不到说明是新元素，插入 oldStartNode 之前
        inesertBefore(UIChildren, newEle, oldStartNode)
      } else {
        // 能找到执行插入操作
        inesertBefore(UIChildren, oldChildren[oldIdx], oldStartNode)

        // 此时oldChildren[oldIdx] 一定处于非边缘位置
        // 而且未通过 while 循环遍历过
        // 所以置空， 再结合对空元素的判断，跳过这个已经被移动的节点
        oldChildren[oldIdx] = undefined 
      }
      // newChildren 的第一个元素处理过了，向右移动
      newStartNode = newChildren[++newStartIdx]
    }
  }

  // 上面循环并不能保证完整遍历两个数组的所有元素
  // 当一个数组遍历完之后，另一个数组可能残留一段区间，尚未遍历到
  // 当 oldChildren 残留区间未遍历 说明要删除这些元素
  // 当 newChildren 残留区间未遍历 说明要新增这些元素
  // 这段区间之内不可能存在可以复用的元素
  if (oldStartIdx > oldEndIdx) {
    // 新增
    // 始终插入到 newChildren[newEndIdx + 1] 之前能维持新插入的元素，从前到后的顺序
    // null 默认插入到最后面
    const before = newChildren[newEndIdx + 1] == null ? null : newChildren[newEndIdx + 1]
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      inesertBefore(UIChildren, newChildren[i], before)
    }
  } else if (newEndIdx < newStartIdx) {
    // 移除
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      removeChild(UIChildren, oldChildren[i])
    }
  }
  return UIChildren
}

代码参见

Inferno / Vue3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
 * @desc inferno & vue3 中采用的最长子序列算法
 * 糅合了前两个算法的一些技巧，再加上最长子序列算法来减少节点的移动操作
 * @param {[number]} oldChildren
 * @param {[number]} newChildren
 */
export function diff(oldChildren, newChildren) {
  const UIChildren = oldChildren.map((v) => v); // clone

  let oldEndIndex = oldChildren.length - 1;
  let newEndIndex = newChildren.length - 1;

  let i = 0;
  let oldEndNode = oldChildren[i];
  let newEndNode = newChildren[i];

  // 类似 vue 2 的算法，进行双向比较
  outer: {
    // 从数组前面开始比对
    while (oldEndNode === newEndNode) {
      i++;
      // 一旦有一个数组遍历完成，跳出执行块
      if (i > oldEndIndex || i > newEndIndex) {
        break outer;
      }
      oldEndNode = oldChildren[i];
      newEndNode = newChildren[i];
    }

    // 从数组后面开始比对
    oldEndNode = oldChildren[oldEndIndex];
    newEndNode = newChildren[newEndIndex];
    while (oldEndNode === newEndNode) {
      newEndIndex--;
      oldEndIndex--;
      // 一旦有一个数组遍历完成，跳出执行块
      if (i > oldEndIndex || i > newEndIndex) {
        break outer;
      }
      oldEndNode = oldChildren[oldEndIndex];
      newEndNode = newChildren[newEndIndex];
    }
  }

  if (i > oldEndIndex && i <= newEndIndex) {
    // i > oldIndex 说明 oldChildren 已经遍历完成
    // i <= newIndex 说明 newChildren 尚未遍历完
    // 此时，这些遍历完的 newChildren 元素一定是需要新增的
    // 新增操作
    const refNode = newChildren[newEndIndex + 1] == null ? null: newChildren[newEndIndex + 1]
    while(i <= newEndIndex) {
      inesertBefore(UIChildren, newChildren[i++] ,refNode)
    }
  } else if (i > newEndIndex) {
    // newChildren 已经遍历完
    // oldChildren 已经暂未遍历完成
    // 此时，这些未遍历完的oldChildren 元素一定是需要移除的
    // 移除操作
    while(i <= oldEndIndex) {
      removeChild(UIChildren, oldChildren[i++])
    }
  } else {
    // 上边处理了比较简单的情况

    const newRemaining = newEndIndex - i + 1 // newChildren 中未处理节点数量
    const source = new Array(newRemaining).fill(-1) // 用来保存未处理的 newChildren 区间元素对应的元素在 oldChildren 的 index

    const oldStartIdx = i
    const newStartIdx = i
    let shouldMove = false
    let lastIndex = 0
    const keyIndexMap = {} // { value/key: index } newChildren未处理区间索引表
    for (let k = newStartIdx; k <= newEndIndex; k++) {
      keyIndexMap[newChildren[k]] = k
    }
    let patched = 0
    
    // 遍历 oldChildren 剩余节点
    for (let i = oldStartIdx; i <= oldEndIndex; i++) {
      const oldNode = oldChildren[i]
      if (patched < newRemaining) {
        const k = keyIndexMap[oldNode] // 找到 oldNode 在 newChildren 中的 index
        if (typeof k !== 'undefined') {
          patched ++
          source[k - newStartIdx] = i

          // 判断是否需要移动，类似 React 的 diff 的思路
          if (k < lastIndex) {
            shouldMove = true
          } else {
            lastIndex = k
          }
        } else {
          // 在 newChildren 中找不到了，移除
          removeChild(UIChildren, oldNode)
        }
      } else {
        // 此时的 oldChildren 未遍历完成， newChildren 已经遍历完成
        // 剩余的oldChildren 中的元素未出现在 newChildren，应当被移除
        removeChild(UIChildren, oldNode)
      }
    }

    if (shouldMove) {
      const seq = lis(source) // 返回最长增长子序列 index 数组
      let j = seq.length - 1

      // 处理未处理的 newChildren 区间
      for(let i = newRemaining - 1; i>= 0; i --) {
        if (source[i] === -1) {
          // 不存在说明是新节点，直接插入到上一个节点处理好的节点即可
          const curIndex = i + newStartIdx
          const newNode = newChildren[curIndex]
          const refNode = newChildren[curIndex + 1] == null ? null : newChildren[curIndex + 1]
          inesertBefore(UIChildren, newNode, refNode)
        } else if (i !== seq[j]) {
          // 说明该节点需要移动
          // 其实和上面的 if 处理逻辑一致
          const curIndex = i + newStartIdx
          const newNode = newChildren[curIndex]
          const refNode = newChildren[curIndex + 1] == null ? null : newChildren[curIndex + 1]
          inesertBefore(UIChildren, newNode, refNode)
        } else {
          // i === seq[j] 说明当前节点在增长子序列中，无需移动
          // j 往前移动
          j--
        }
      }
    }
  }
  return UIChildren;
}

代码参见

参考

FE
14 minutes read (About 2096 words)

TS 一些工具泛型的使用及其实现(续)

之前写了一篇 TS 一些工具泛型的使用及其实现, 但是一直没怎么使用 TS，回首看文章，发现自己都看不懂了。
期间内 TS 也有一些变化，所以这一篇将会承接上篇文章，分析解读更多的工具泛型，主要来自 utility-types项目的源码。
阅读本流水账需要对 TS 中的以下东西有所了解

  • extends
  • keyof
  • in
  • infer
  • &
  • |
  • ?
  • -?
  • +?
  • never
  • unkown
  • any
  • readonly
  • void

正文

ArrayElement

提取数组成员类型,
一个思路是 用 extends 限制数组类型, 然后用数组 key 类型为 number 的特性取出其属性类型

1
type ArrayElement<T extends readonly unknown[]> = T[number];

第二种写法的核心思路就是用 infer 来隐射 数组的属性类型

1
type ArrayElement<A> = A extends readonly (infer T)[] ? T : never

Exclude & Extract vs. Diff & Filter

TS 内置类型定义涵盖了 Exclude & Extract, 但是在它的官方文档又给出了另外的名字

1
2
type Diff<T, U> = T extends U ? never : T;
type Filter<T, U> = T extends U ? T : never;

就类型定义的代码而言，Exclude === Diff, Extract === Filter，蜜汁操作

NonNullable

从类型 T 中排除 null 和 undefined

1
type NonNullable<T> = Exclude<T, null | undefined>

Parameters

拿到函数的参数类型，不定参数的组织形式就是一个数组，参考 ArrayElement的第二种写法，利用infer去取到类型

1
type Parameters<T extends (...args: any) => any> = T extends (...args: infer P) =>  any ? P : never

ConstructorParameters

要拿到构造函数参数的类型，参考 Parameters，加上 new 即可

1
type ConstructorParameters<T extends new (...args: any) => any> = T extends new (...args: infer P) =>  any ? P : never

InstanceType

获取实例类型，跟 Parameters 和 ConstructorParameters 差不多，不过这次不 infer 参数了，而是 infer 函数返回数据

1
type InstanceType<T extends new (...args: any) => any> = T extends new (...args: any) =>  infer R ? R : never
Read More
FE
3 minutes read (About 523 words)

Lodash get 三个基础实现版本

接上篇，在 Vue 中你可以 这样 a.b.c.d 进行 watch，在 lodash 你也可以以同样的形式进行属性的读取，思索其中中源码实现才有了这篇文章
_.get 基本语法

1
2
3
4
5
6
7
// 基本语法
_.get(obj, path, "defaultValue");

_.get(obj, "a.b[0].c", "defaultValue");

// 或者 path 以数组的形式
_.get(obj, ["a", "b", "0", "c"], "defaultValue");

path 支持两种形式的传值，数组和字符串，我们需要转成统一的数组形式，便于取值

Read More
FE
5 minutes read (About 742 words)

JS 最近进入 Stage 4 的两个提案

今天刷推特的时候看到 TC39 的成员说 js 的两个语法糖提案进入 stage 4，最终板上钉钉，修成正果。

  • Optional Chaining
  • Nullish Coalescing
    其中 Optional Chaining 在这之前的 TS 3.7 中就被引入了

Optional Chaining

在此之前使用我们通常获取一个多层级对象一个比较内层的属性，为了避免为空的情况不得不这样写

1
let prop = a.b && a.b.c && a.b.c.d // 取到值或者赋值为 undefined

习惯了 Lodash 之后

1
let prop = _.get(a, "b.c.d", undefined) // 可以自定义默认值

使用 Optional Chaining 之后

1
let prop = a?.b?.c?.d
Read More
FE
4 minutes read (About 553 words)

关于 Vue 的一些冷门技巧

watch

有时候我们会写一些这样的代码, 在 created 一个组件之后获取数据, 然后根据某个值得变动来获取数据, 正常套路是按照下面写的,

1
2
3
4
5
6
7
8
created() {
 this.fetchUserList()
},
watch: {
  searchText () {
    this.fetchUserList ()
  }
}

但是 watch 的 api 其实很复杂, 语法糖甜的掉牙了. 于是我们可以简化为

Read More
FE
8 minutes read (About 1260 words)

Rxjs Scheduler 下的 eventloop

本文将简单介绍 event loop 在 RxJS 中运用. 偏重于 RxJS Scheduler 而不是 event loop

event loop

event loop 是一种任务调度机制, 用来处理异步任务, 在 JavaScript 单线程语言中, 在同一时间内只能只能处理一件事, 当我们遇到需要处理异步的情况, 不能让异步操作阻塞线程, 我们可以让异步任务先搁置, 先执行同步任务, 等异步时间来临再来执行异步任务, 这就是 event loop.

JavaScript 在执行过程中, 变量与对象会存入对中, 另外还会维护一个任务队列(包括宏任务队列, 微任务队列), 执行函数会被推入栈中, 一旦函数执行完毕就会从函数中推出, 一旦整个执行栈被清空, 就开始处理任务队列, 按照一定逻辑将任务推入执行栈中执行, 执行过程中可能会往任务队列中添加其他任务,微任务具有高优先级, 在单个宏任务的切换中间会检查执行整个微任务队列, 再去执行下一个宏任务

Read More
FE
2 minutes read (About 365 words)

Vue 异步计算属性实现

前段时间在 GitHub 上看到一个 Vue 异步计算属性的库 - vue-async-computed, 将异步操作转化为计算属性, 例如这样用

1
2
3
4
5
6
7
8
9
10
11
new Vue({
  data: {
    userId: 1
  },
  asyncComputed: {
    username () {
      return Vue.http.get('/get-username-by-id/' + this.userId)
        .then(response => response.data.username)
    }
  }
}

好奇其中原理, 看了源码, 了解其中巧妙的实现思路, 绘制了一张核心思路的原型图.

接下来我们实现一个简(阉)易(割)版本的 vue-async-computed 插件,

趁着 beforeCreate 往 data 中添加 asyncComputed 的 key, 使之响应式.

Read More
FE
8 minutes read (About 1176 words)

TS 一些工具泛型的使用及其实现

本文将简要介绍一些工具泛型使用及其实现, 这些泛型接口定义大多数是语法糖(简写), 甚至你可以在 typescript 包中的 lib.d.ts 中找到它的定义, 最新版的 typescript (2.9) 已经包含了大部分, 没有包含的我会特别指出.

Partial

Partial 作用是将传入的属性变为可选项.
首先我们需要理解两个关键字 keyof 和 in, keyof 可以用来取得一个对象接口的所有 key 值.
比如

Read More
FE
4 minutes read (About 634 words)

使用装饰器自动取消订阅 React 组件中的 RxJS 流

最近自己的一个项目使用了 RxJS 进行状态管理, 需要在组件中订阅流来获取全局状态， 但是在组件卸载的时候需要手动取消订阅流.
这样写起来有点繁琐，所以考虑用装饰器简化下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import * as React from "react";
import { Subscription } from "rxjs";
import { action$, state$ } from "../store/store";

class Artist extends React.Component {
  sub: Subscription;
  handleClick() {
    setInterval(() => {
      action$.next((state: any) => state);
    }, 1000);
  }
  componentDidMount() {
    this.sub = state$.subscribe(v => {
      console.log("artist", v);
    });
  }
  componentWillUnmount() {
    console.log("artist unsubscribe");
    this.sub.unsubscribe();
  }
  render() {
    return (
      <div>
        <button onClick={() => this.handleClick()}>Click Me</button>
      </div>
    );
  }
}

export default Artist;
Read More
FE
5 minutes read (About 676 words)

装饰器学习

前言

一直觉得装饰器的写法有种蜜汁好感和好奇，例如 @component或者@connect(x, y)。

装饰器在 React 和 Angular 中很常见，因为这两个框架很强调类，而装饰器的作用范围正是类和类成员，来看装饰器提案的一句话

Decorators make it possible to annotate and modify classes and properties at design time.

指出了装饰器作用对象，注意到最后三个单词 at design time, 再抄袭一句话

装饰器对类的行为的改变，是代码编译时发生的，而不是在运行时。这意味着，装饰器能在编译阶段运行代码。也就是说，装饰器本质就是编译时执行的函数

Read More

Categories

Archives

Recent

Tags

Recent

Tags

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×