{"action":"created","issue":{"url":"https://api.github.com/repos/NervJS/nerv/issues/3","repository_url":"https://api.github.com/repos/NervJS/nerv","labels_url":"https://api.github.com/repos/NervJS/nerv/issues/3/labels{/name}","comments_url":"https://api.github.com/repos/NervJS/nerv/issues/3/comments","events_url":"https://api.github.com/repos/NervJS/nerv/issues/3/events","html_url":"https://github.com/NervJS/nerv/issues/3","id":274447543,"number":3,"title":"diff 算法原理概述","user":{"login":"yuche","id":7202516,"avatar_url":"https://avatars2.githubusercontent.com/u/7202516?v=4","gravatar_id":"","url":"https://api.github.com/users/yuche","html_url":"https://github.com/yuche","followers_url":"https://api.github.com/users/yuche/followers","following_url":"https://api.github.com/users/yuche/following{/other_user}","gists_url":"https://api.github.com/users/yuche/gists{/gist_id}","starred_url":"https://api.github.com/users/yuche/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuche/subscriptions","organizations_url":"https://api.github.com/users/yuche/orgs","repos_url":"https://api.github.com/users/yuche/repos","events_url":"https://api.github.com/users/yuche/events{/privacy}","received_events_url":"https://api.github.com/users/yuche/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":6,"created_at":"2017-11-16T09:28:46Z","updated_at":"2018-04-24T12:45:30Z","closed_at":"2018-01-10T16:01:45Z","author_association":"CONTRIBUTOR","body":"1. 找到相同的前置元素和后置元素\r\n\r\n```\r\n     *\r\n     *  A: -> [a b c d] <-\r\n     *  B: -> [a b d] <-\r\n     *\r\n```\r\n这里我们可以发现前置元素 a, b 和 后置元素 d 都是相同的。所以我们可以将这样的 diff 情况转变为：\r\n```\r\n\r\n     *\r\n     *  A: -> [c] <-\r\n     *  B: -> [] <-\r\n     *\r\n\r\n```\r\n这里我们可以发现 A 和 B 的不同就是多了一个 c 元素，所以只要进行把 c 元素移除这一步可以完成 diff。相反地，如果这步操作 A 为空，B 有多余元素，那么我们就将多余元素插入即可。\r\n这一步 diff 优化最早由 [Neil Fraser](https://neil.fraser.name/writing/diff/) 提出，实现非常简单（在 Neil 的文章里他提供了 JavaScript，Java，Python 三种实现），优化的力度也非常大，但真正首次应用到前端框架却是十年后的 Bobril，后来号称性能最强的 Inferno 也使用了这一优化。\r\n\r\n再来看下一种情况：\r\n```\r\n\r\n     *\r\n     *  A: -> [a b c d e f g] <-\r\n     *  B: -> [a c b h f e g] <-\r\n     *\r\n\r\n```\r\n在这个情况的 diff 中，我们可以应用之前的优化策略把他简化为：\r\n\r\n```\r\n     *\r\n     *  A: -> [b c d e f] <-\r\n     *  B: -> [c b h f e] <-\r\n     *\r\n```\r\n\r\n2. 这时候我们就需要进行第二步：找到需要被删除、插入或移动的元素：\r\n\r\n首先我们创造一个数组 `P`，它代表新数组应该被插入的位置。\r\n\r\n```\r\n     *\r\n     *  A: [b c d e f]\r\n     *  B: [c b h f e]\r\n     *  P: [. . . . .] // . == -1\r\n     *\r\n```\r\n\r\n接下来我们再创建一个索引 `I`，作为新数组位置的映射（如果新旧数组都很小的话，那我们直接遍历数组即可，反之我们需要一个索引）：\r\n\r\n```\r\n     *\r\n     *  A: [b c d e f]\r\n     *  B: [c b h f e]\r\n     *  P: [. . . . .] // . == -1\r\n     *  I: {\r\n     *    c: 0,\r\n     *    b: 1,\r\n     *    h: 2,\r\n     *    f: 3,\r\n     *    e: 4,\r\n     *  }\r\n     *  last = 0\r\n     *\r\n```\r\n\r\n有了数组 `P` 和 索引 `I` 之后，现在我们可以开始遍历旧数组\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n * \t^\r\n *  B: [c b h f e]\r\n *  P: [. 0 . . .] // . == -1\r\n *  I: {\r\n *    c: 0,\r\n *    b: 1, <-\r\n *    h: 2,\r\n *    f: 3,\r\n *    e: 4,\r\n *  }\r\n *  last = 1\r\n *\r\n```\r\n第一步遍历我们可以发现旧数组的 b 元素也在新数组上，所以我们把他在旧数组的位置 0 放到他在数组 P 相对应的位置上。\r\n\r\n这里我们同时还要维护一个变量 last，它代表访问过的节点在旧集合中最右的位置(即最大的位置)。如果新集合中当前访问的节点比 last 大，说明当前访问节点在旧集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不必执行移动操作。只有当访问的节点比 last 小时，才需要进行移动操作。 \r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n * \t  ^\r\n *  B: [c b h f e]\r\n *  P: [1 0 . . .] // . == -1\r\n *  I: {\r\n *    c: 0, <-\r\n *    b: 1,\r\n *    h: 2,\r\n *    f: 3,\r\n *    e: 4,\r\n *  }\r\n *  last = 1 // last > 0; moved = true\r\n *\r\n```\r\n\r\n这里我们访问元素 c 的位置为 0，而 last 为 1，所以我们需要进行移动操作。\r\n\r\n这一步实际上也是 React Stack Reconciler（React 16 以下）的核心算法：每次遍历的时候把当前节点在旧集合的位置和 last 进行对比，如果 mountIndex 大于 last，那么就把他添加到差异队列，然后更新 last，全部遍历完毕之后再遍历差异队列，一步一步进行 patch。\r\n\r\n（这里如果理解有障碍的话建议把常规的排序算法都撸一遍，可以重点看选择排序和插入排序）\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *          ^\r\n *  B: [c b h f e]\r\n *  P: [1 0 . . .] // . == -1\r\n *  I: {\r\n *    c: 0,\r\n *    b: 1,\r\n *    h: 2,\r\n *    f: 3,\r\n *    e: 4,\r\n *  }\r\n *  moved = true\r\n *\r\n```\r\n这里元素 d 在新数组当中并不存在，所以它应该被移除掉。\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *            ^\r\n *  B: [c b h f e]\r\n *  P: [1 0 . . 3] // . == -1\r\n *  I: {\r\n *    c: 0,\r\n *    b: 1,\r\n *    h: 2,\r\n *    f: 3,\r\n *    e: 4, <-\r\n *  }\r\n *  moved = true\r\n```\r\n\r\n这里把元素 e 在旧数组的位置（3）放到数组 `P` 上。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n * \t        ^\r\n *  B: [c b h f e]\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  I: {\r\n *    c: 0,\r\n *    b: 1,\r\n *    h: 2,\r\n *    f: 3, <-\r\n *    e: 4,\r\n *  }\r\n *  moved = true\r\n *\r\n```\r\n这里把元素 f 在旧数组的位置（4）放到数组 `P` 上。\r\n\r\n到了这一步，如果是 React 的算法已经走完了。但不妨思考以下的 diff 情况：\r\n```\r\n *\r\n * A: [a b c d]\r\n * B: [d a b c]\r\n *\r\n```\r\n这里肉眼一看就知道，把旧集合的 d 元素移动到 0 这一步操作就可以完成 diff。但根据前文所述的逻辑走一次，实际上 React 会先把 a, b, c 移动到他们的相应的位置 + 1，一共三步操作。\r\n\r\n移动操作也并不是没有副作用，仍然可能会重启动画，focus 丢失，重置滚动条位置等。所以我们还可以进行下一步优化：\r\n\r\n3. 找到最小的移动次数。\r\n\r\n这里我们需要找到 `P` 数组的[最长递增子序列(longest increasing subsequence)] 来做动态规划，新集合中不属于这个序列的将会被移动。\r\n\r\n还是用我们之前的例子：\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  LIS:     [1 4]\r\n *  moved = true\r\n *\r\n```\r\n\r\n这里我们同时尾部遍历新数组和 LIS 序列，查看元素的位置是否能与 LIS 序列的任何一个值匹配。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *              ^  // new_pos == 4\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  LIS:     [1 4]\r\n *              ^  // new_pos == 4\r\n *  moved = true\r\n *\r\n```\r\n这一步能匹配，e 可以呆在它原来的位置上。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *            ^    // new_pos == 3\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  LIS:     [1 4]\r\n *            ^    // new_pos != 1\r\n *  moved = true\r\n *\r\n```\r\n\r\nf 的位置不能匹配，把他移动到 e 之前。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *          ^      // new_pos == 2\r\n *  P: [1 0 . 4 3] // . == -1\r\n *          ^      // old_pos == -1\r\n *  LIS:     [1 4]\r\n *            ^\r\n *  moved = true\r\n *\r\n```\r\nh 的位置为 -1，把他插入。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *        ^        // new_pos == 1\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  LIS:     [1 4]\r\n *            ^    // new_pos == 1\r\n *  moved = true\r\n *\r\n```\r\nb 能匹配 LIS，可以老老实实呆着。\r\n\r\n```\r\n *\r\n *  A: [b c d e f]\r\n *  B: [c b h f e]\r\n *      ^          // new_pos == 0\r\n *  P: [1 0 . 4 3] // . == -1\r\n *  LIS:     [1 4]\r\n *          ^      // new_pos != undefined\r\n *  moved = true\r\n *\r\n```\r\nc 不能匹配，把它移动到 b 之前。\r\n\r\n走完这一步我们的 diff 算法就完毕了。\r\n\r\n这时回头再来看看之前把尾部元素插入到头部的情况，React 需要经过 3 次操作，而经过我们动态规划之后：\r\n```\r\n *\r\n - A: [a b c d]\r\n - B: [d a b c]\r\n - P: [3 0 1 2]\r\n - LIS: [0 1 2]\r\n *\r\n```\r\n可以发现 a, b, c 能匹配 LIS，可以呆到天荒地老，我们只要把 d 移动到头部的位置就可以完成 diff。Perfect！\r\n\r\n详细代码：\r\nhttps://github.com/NervJS/nerv/blob/patch/packages/nerv/src/vdom/patch.ts"},"comment":{"url":"https://api.github.com/repos/NervJS/nerv/issues/comments/383916771","html_url":"https://github.com/NervJS/nerv/issues/3#issuecomment-383916771","issue_url":"https://api.github.com/repos/NervJS/nerv/issues/3","id":383916771,"user":{"login":"yuche","id":7202516,"avatar_url":"https://avatars2.githubusercontent.com/u/7202516?v=4","gravatar_id":"","url":"https://api.github.com/users/yuche","html_url":"https://github.com/yuche","followers_url":"https://api.github.com/users/yuche/followers","following_url":"https://api.github.com/users/yuche/following{/other_user}","gists_url":"https://api.github.com/users/yuche/gists{/gist_id}","starred_url":"https://api.github.com/users/yuche/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuche/subscriptions","organizations_url":"https://api.github.com/users/yuche/orgs","repos_url":"https://api.github.com/users/yuche/repos","events_url":"https://api.github.com/users/yuche/events{/privacy}","received_events_url":"https://api.github.com/users/yuche/received_events","type":"User","site_admin":false},"created_at":"2018-04-24T12:45:30Z","updated_at":"2018-04-24T12:45:30Z","author_association":"CONTRIBUTOR","body":"我猜这类文章指的是整棵树的对比是 O(n ^ 3)，而 React 只对比同级元素，并且他们的 `type` 和 `key` 是一致才继续 diff (包括他们 children)下去，否则就直接替换或删除掉。从这个意义上来讲，这些文章也没有讲错。"}}
{"actor":{"display_login":"yuche"}}