git 有一条命令：

00$ git diff

它会标出你在哪修改了文件，是 modified 还是 add 还是 delete，都会帮你标注，这里面用到了 diff 算法。

diff 操作，本质上是找出对象间的增量差异，比如 diff 如下两个数组：

00let a = [1, 2, 3, 4]; 
01let b = [2, 3, 1]; 
02
03diff(a, b);

diff 结果可以是：

取出 1 放到最后面
删除 4

显然 diff 结果可能有很多，diff 问题是一类动态规划问题，找到最优的路径是 diff 算法所追求的。

现在来谈谈虚拟 DOM 的 diff / patch 问题，若读者无意于实现，本篇可以跳过不看了（本篇基本上是 Code）

虚拟DOM 的 diff 算法是他的核心算法，非常直接地决定了性能。，我在这一步卡了很长时间，先是使用了其他人的库，但是有 bug （diff 结果错误），不得已自己实现了一个简单的 diff 算法。

# 虚拟 DOM 里的 diff 操作 ↵

那么虚拟 DOM 里的 diff 操作呢？

00<div id="app1">
01    <p>Apple</p>
02    <p>eczn</p>
03    <p>Star</p>
04</div>
05
06<div id="app2">
07    <p>Star</p>
08    <p>eczn</p>
09</div>

app1 跟 app2 的 diff 结果：

删除 Apple
Star 和 eczn 互换位置

在虚拟 DOM 中为了便于实现，应该加上 vid 去表达节点：

00<div id="app1">
01    <p vid="1">Apple</p>
02    <p vid="2">eczn</p>
03    <p vid="3">Star</p>
04</div>
05
06<div id="app2">
07    <p vid="3">Star</p>
08    <p vid="2">eczn</p>
09</div>

这样问题就化为下面两个数组的 diff 问题了：

00let app1_vids = ["1", "2", "3"]; 
01let app2_vids = ["3", "2"]; 
02
03diff(app1_vids, app2_vids);

解决虚拟 DOM 的 diff 问题其实就是要解决数组的 diff 问题。

# diff 算法的一个实现 ↵

本来我打算用其他人的 diff 去做的，但发现使用的过程中有bug （结果不对），因此自己实现了一个（性能不算最好的，但是能用）

我先贴出使用方式，文末会贴出源码：

00let list_diff = require('path/to/list-diff.js'); 
01
02// 打开 debug 模式 
03list_diff.debug = true; 
04
05// 元素为对象 
06let patches_1 = list_diff(
07    [{ id: '1'}, { id: '2' }, { id: '3' }], 
08    [{ id: '3'}, { id: '1' }], 
09    'id' // 标出 id 的字段 
10); 
11
12// 或者一般情况下 
13let patches_2 = list_diff(
14    [1, 2, 3, 4, 5, 6], 
15    [2, 3, 6, 5, 9]
16);

命令行输出的结果为：

00diff A
01当前:
02[ '1', '2', '3' ]
03目标:
04[ '3', '1' ]
05
06
07当前 idx 0 当前 len 3
08[ '1', '2', '3' ]
09a 跟 b 不一样
10在 2 处找到了跟 b 一样的，交换跟当前的一下 3
11
12
13当前 idx 1 当前 len 3
14[ '3', '2', '1' ]
15a 跟 b 不一样
16在 2 处找到了跟 b 一样的，交换跟当前的一下 1
17
18
19当前 idx 2 当前 len 3
20[ '3', '1', '2' ]
21b 不存在, 应该剔除
22
23
24[ '3', '1' ]
25[ '3', '1' ]
26Array {
27  '0': { type: 'REORDER', idx: 0, item: 2 },
28  '1': { type: 'REORDER', idx: 1, item: 2 },
29  '2': { type: 'DELETE', idx: 2 },
30  length: 3 }
31
32DIFF TIME: 9.396ms
33
34
35
36diff B
37当前:
38[ 1, 2, 3, 4, 5, 6 ]
39目标:
40[ 2, 3, 6, 5, 9 ]
41
42
43当前 idx 0 当前 len 6
44[ 1, 2, 3, 4, 5, 6 ]
45a 跟 b 不一样
46在 1 处找到了跟 b 一样的，交换跟当前的一下 2
47
48
49当前 idx 1 当前 len 6
50[ 2, 1, 3, 4, 5, 6 ]
51a 跟 b 不一样
52在 2 处找到了跟 b 一样的，交换跟当前的一下 3
53
54
55当前 idx 2 当前 len 6
56[ 2, 3, 1, 4, 5, 6 ]
57a 跟 b 不一样
58在 5 处找到了跟 b 一样的，交换跟当前的一下 6
59
60
61当前 idx 3 当前 len 6
62[ 2, 3, 6, 4, 5, 1 ]
63a 跟 b 不一样
64在 4 处找到了跟 b 一样的，交换跟当前的一下 5
65
66
67当前 idx 4 当前 len 6
68[ 2, 3, 6, 5, 4, 1 ]
69a 跟 b 不一样
70找不到，应该插入
71
72
73当前 idx 5 当前 len 7
74[ 2, 3, 6, 5, 9, 4, 1 ]
75b 不存在, 应该剔除
76
77
78[ 2, 3, 6, 5, 9, 1 ]
79[ 2, 3, 6, 5, 9 ]
80Array {
81  '0': { type: 'REORDER', idx: 0, item: 1 },
82  '1': { type: 'REORDER', idx: 1, item: 2 },
83  '2': { type: 'REORDER', idx: 2, item: 5 },
84  '3': { type: 'REORDER', idx: 3, item: 4 },
85  '4': { type: 'INSERT', idx: 4, item: 9 },
86  '5': { type: 'DELETE', idx: 5 },
87  '6': { type: 'DELETE', idx: 5 },
88  length: 7 }
89
90DIFF TIME: 5.612ms

# patch 操作 ↵

把 diff 的结果应用到对应的数组里。

00let list_diff = require('path/to/list-diff.js'); 
01
02let a = [1, 2, 3, 4, 5, 6]; 
03let b = [2, 3, 6, 5, 9]
04
05// 或者一般情况下 
06let patches = list_diff(a, b); 
07
08patches.to(a); 
09
10console.log(a); 
11// => 
12// [2, 3, 6, 5, 9]

# list-diff.js ↵

以下，是源码，比较长：

000// CONST VAR 
001// 用字符串比数组更直观，但相对的性能稍差点
002const INSERT  = 'INSERT'  || 0  // 插入 
003    , REORDER = 'REORDER' || 1  // 交换 
004    , DELETE  = 'DELETE'  || 2  // 删除
005
006_diff.INSERT  = INSERT ; 
007_diff.REORDER = REORDER; 
008_diff.DELETE  = DELETE ; 
009
010// EXPORT
011module.exports = _diff; 
012
013/**
014 * @description KeyMap, 相当于 arr.map(e => e[key])
015 * @param { Array } arr 
016 * @param { String | Number } key 
017 */
018function keyMap(arr, key){
019    let len = arr.length; 
020    let res = [];
021    for (let i = 0; i < len; i++){
022        res[i] = arr[i][key]; 
023    }
024    return res; 
025}
026
027/**
028 * @description Patches 
029 */
030function Patches(){
031    this.length = 0; 
032}
033
034// 继承自 Array 
035let PP = Object.create(Array.prototype); 
036// 连接 
037Patches.prototype = PP; 
038
039/**
040 * @description 把 Patches 应用到 list_a 
041 * @param   { Array }  list_a 
042 * @returns { Array }  list_a 
043 */
044Patches.prototype.to = function(list_a){
045    this.forEach(patch => {
046        let { type, idx, item } = patch; 
047    
048        if (type === DELETE){
049            list_a.splice(idx, 1); 
050        } else if (type === INSERT){
051            list_a.splice(idx, 0, item); 
052        } else if (type === REORDER){
053            let exIdx = item; 
054            let a = list_a[idx]; 
055            
056            list_a[idx]   = list_a[exIdx]; 
057            list_a[exIdx] = a; 
058        }
059    }); 
060
061    return list_a;
062}
063
064/**
065 * @description 数组 diff 跳板
066 * @param { Array<String | Number> } list_a 
067 * @param { Array<String | Number> } list_b 
068 * @returns { Patches } 返回 patch
069 */
070function _diff(list_a_obj, list_b_obj, key){
071    // 复制数组 
072    let list_a, list_b, list_b_key_map; 
073    if (key){
074        // list_a = list_a_obj.map(e => e[key]); 
075        list_a = keyMap(list_a_obj, key); 
076        // list_b = list_b_obj.map(e => e[key]); 
077        list_b = keyMap(list_b_obj, key); 
078        list_b_key_map = val_2_idx(list_b_obj, key)
079    } else {
080        list_a = list_a_obj; 
081        list_b = list_b_obj; 
082    }
083
084    let list_copy_from_a = list_a.slice(); 
085
086    let patches = new Patches(); 
087    
088    // 确保 diff 的第一个参数 list_a 是副本
089    return diff(list_copy_from_a, list_b, key, list_b_obj, list_b_key_map, patches); 
090}
091
092
093/**
094 * @description 反转数组键值对 
095 * @param { Array<String | Number> } list 
096 * @param { String | Number } key 
097 * @returns { Array< * > }
098 */
099function val_2_idx(list_obj, key){
100    let list = keyMap(list_obj, key); 
101    
102    return list.reduce((acc, cur, idx) => {
103        acc[cur] = list_obj[idx]; 
104        return acc; 
105    }, {}); 
106}
107
108/**
109 * @description 数组 diff 
110 * @param   { Array<String | Number> }  list_a 
111 * @param   { Array<String | Number> }  list_b 
112 * @param   { Patches } patches
113 * @returns { Patches } patches
114 */
115function diff(list_a, list_b, key, list_b_obj, list_b_key_map, patches){   
116    const DEBUG = !!_diff.debug;
117
118    let len = Math.max(list_a.length, list_b.length)
119    
120    // console.log(list_a); 
121    DEBUG && (
122        console.time('DIFF'), 
123        console.log('当前: '),
124        console.log(list_a), 
125        console.log('目标: '),
126        console.log(list_b), 
127        console.log('\n')
128    ); 
129
130    for (let idx = 0; idx < len; idx ++){
131        let a = list_a[idx]; 
132        let b = list_b[idx]; 
133
134        DEBUG && (
135            console.log('当前 idx', idx, '当前 len', len),
136            console.log(list_a)
137        ); 
138        
139        if (!a){
140            DEBUG && (
141                console.log('a 不存在, 应该插入')
142            ); 
143            // a 不存在 
144            // 说明 list_b 比 list_a 长，应插入 b  
145            patches.push({
146                type: INSERT, 
147                idx: idx, 
148                item: key ? list_b_key_map[b] : b
149            }); 
150
151            // 在 list_a 上插入
152            DEBUG && (
153                console.log('b:', b)
154            ); 
155            list_a.push(b); 
156        } else if (!b){
157            DEBUG && (
158                console.log('b 不存在, 应该剔除')
159            ); 
160            // b 不存在 
161            // 说明 list_b 比 list_a 短，a 多余, 应剔除 
162            patches.push({
163                type: DELETE,
164                idx: idx
165            }); 
166            // 在 list_a 上剔除 
167            list_a.splice(idx, 1); 
168        } else {
169            if (b === a){
170                DEBUG && (
171                    console.log('a 刚好根 b 一样')
172                ); 
173                // 命中，跳过 
174                // do nothing 
175
176            } else { // b !== a
177                DEBUG && (
178                    console.log('a 跟 b 不一样')
179                ); 
180                // 这个位置上应该是 b, 但是目前是 a 
181                // 所以首先应该找找看看 list_a 里有没有 b, 有的话就根这里交换位置
182                // 否则插入到这里 
183                let exIdx_relative = list_a.slice(idx).findIndex(e => e === b); 
184                
185                if (~exIdx_relative){ // list_a 之后存在 b, 则交换位置 
186                    let exIdx = exIdx_relative + idx; 
187
188                    DEBUG && (
189                        console.log('在', exIdx, '处找到了跟 b 一样的，交换跟当前的一下', b)
190                    ); 
191                    patches.push({
192                        type: REORDER, 
193                        idx: idx, 
194                        item: exIdx
195                    }); 
196                    list_a[idx]   = list_a[exIdx]; 
197                    list_a[exIdx] = a; 
198                } else {     // 找不到插入  
199                    DEBUG && (
200                        console.log('找不到，应该插入')
201                    ); 
202                    patches.push({
203                        type: INSERT, 
204                        idx: idx, 
205                        item: key ? list_b_key_map[list_b_obj[idx][key]] : b
206                    }); 
207
208                    list_a.splice(idx, 0, b); 
209                }
210            }
211        }
212
213        // 更新一下 
214        len = Math.max(list_a.length, list_b.length); 
215
216        DEBUG && (
217            console.log('\n')
218        ); 
219    }
220
221    // let remain = list_a.slice(list_b.length); 
222    let delta = list_a.length - list_b.length; 
223
224    DEBUG && (
225        // console.log(remain),
226        console.log(list_a),
227        console.log(list_b)
228    ); 
229
230    if (delta > 0){
231        for (let i = delta; i > 0; i--){
232            patches.push({
233                type: DELETE, 
234                idx: list_b.length
235            }); 
236            list_a.pop();
237        }
238    }
239
240    DEBUG && (
241        console.log(patches),
242        console.timeEnd('DIFF')
243    ); 
244
245    return patches; 
246}

# TL;DR ↵

… 总之… diff 很有趣 …

下一篇将会把 list-diff 加入到虚拟 DOM 套餐中 …