diff 算法原理概述

[nervjs]

diff 算法原理概述

[kurtextrem]

I am sorry as I can't speak your language, but I am still interested in this topic, would someone please be so kind to translate it to me? (Google Translator doesn't really work well)

[yuche]

@kurtextrem
Check this out:
https://github.com/adamhaile/surplus/blob/5f5ad8d9e7eb6db954cd146bd48772f77886b295/es/content.js
https://github.com/ivijs/ivi/blob/2c81ead934b9128e092cc2a5ef2d3cabc73cb5dd/packages/ivi/src/vdom/implementation.ts#L12:81
These comments should answer your question.

[zhangchen91]

可以发现 a, b, c 能匹配 LIS?

[yuche]

@zhangchen91 改了，谢谢。

[zhangchen91]

这个算法看了下，Inferno 也是这么实现的，可否认为建立『索引 I』是一种空间换时间的优化，然后在 LIS 算法上时间复杂度是 O(n) ？个人看资料也是 O(n log n)啊？

想问下之前几种编辑距离(Edit Distance)应该跟 LCS 是对偶问题吧，似乎优化也是到 O(n log n)？因为我有看到有 vdom 算法是用 LCS https://github.com/yelouafi/petit-dom/blob/5412b18ad26108762ebf5624ac1c5bd70c578e57/src/vdom.js#L690

最短编辑距离和最小移动应该算不同的问题吧？毕竟一个针对的是改插删，而后者更针对移动插删？

最近为了看 Diff 算法补了好几篇论文有点头晕还没消化过来，求解惑~

[yuche]

1. 是空间换时间。所以在具体的实现上会设置一个限制，当数组长度太低的时候就不建立索引了，直接遍历全部。大部分性能排行在 js-framwork-bench 前列的框架基本都是用这个算法，ivi 是最早使用的，其他的或多或少都参考了他。

2. 目前没发现可以优化到 O(n) 的算法，你给的链接应该是目前已经实现在 vdom 中最快的算法，期望复杂度是 O(n log n)。

3. 我个人认为是同一件事情，diff 算法的核心就是找最小的编辑距离，找最小移动只是其中的一个方法而已。

[zhangchen91]

了解，那之前好多文章写 React 的 Diff 算法复杂度是从 O(n^3) 优化到 O(n) 要如何理解呢？
children 的这块的复杂度就已经超越了 O(n) 了不是么？
所以 O(n^3) 到 O(n) 的这个优化度的说法，是不包含 children 的部分？
还是说大部分解读的文章有误读呢？或者说是 React 放弃了 children 这块的优化，取了一个 O(n) 的 Patch 解法？

PS：在知乎提了个问，感觉可以把 issue 的内容贴过去宣传一波，https://www.zhihu.com/question/274459523 ，还挺多人关注的

[yuche]

我猜这类文章指的是整棵树的对比是 O(n ^ 3)，而 React 只对比同级元素，并且他们的 type 和 key 是一致才继续 diff (包括他们 children)下去，否则就直接替换或删除掉。从这个意义上来讲，这些文章也没有讲错。

[gu18168]

请问，为何最后一步是尾部遍历新数组 B 呢？明明 P 中存储的是元素在旧数组 A 中的位置。而且如果是遍历新数组的话，尾部元素插入到头部中的 a, b, c 为什么能匹配 LIS，明明他们的新位置是 1, 2, 3 ？
时间隔了很久才发现这篇文章，现在提问打扰了。

[WzFFzW]

请问一下，找到LIS之后，可不可以换成这样

1. 找到LIS
2. 正序遍历新数组，从P中得到元素对应的位置
3. 判断元素所在的位置是不是在LIS中
4. 如果是，就不移动当前元素，如果不是，就移动当前元素到对应位置。

不知道这样和你的思路是否一样，（因为我没看代码，所以不清楚你的代码是不是这样的思路）

[oychao]

细节太多了，光看这个能懂个80%左右，第3步“找到最小的移动次数”还是看了源码才懂，算法核心已经实现了，感谢作者，受益匪浅~

[triboby]

 *
 *  A: [b c d e f]
 *            ^
 *  B: [c b h f e]
 *  P: [1 0 . . 3] // . == -1
 *  I: {
 *    c: 0,
 *    b: 1,
 *    h: 2,
 *    f: 3,
 *    e: 4, <-
 *  }
 *  moved = true

e这步的moved是false ？

[wizardpisces]

 *
 *  A: [b c d e f]
 *            ^
 *  B: [c b h f e]
 *  P: [1 0 . . 3] // . == -1
 *  I: {
 *    c: 0,
 *    b: 1,
 *    h: 2,
 *    f: 3,
 *    e: 4, <-
 *  }
 *  moved = true

e这步的moved是false ？

按照他的表述确实应该是 false，但是通篇看下来并没发现moved的作用，主要就是通过新旧数组来生成那个变化数组