-
Notifications
You must be signed in to change notification settings - Fork 3.3k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
第 97 题:React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ,那么 O(n^3) 和 O(n) 是如何计算出来的? #151
Comments
好问题:fist: |
我理解的是:react对比按照树的层级去对比,给树节点编号0,1,2,3...,相同编号对比,不一样就直接删除然后,添加新节点, |
react只做了同层比较,同级的节点类型不同就认为不同,重新渲染。 |
我认为react做了三种优化来降低复杂度:1:如果父节点不同,放弃对子节点的比较,直接删除旧节点然后添加新的节点重新渲染;2:如果子节点有变化,Virtual DOM不会计算变化的是什么,而是重新渲染,3:通过唯一的key策略 |
我知道,但是我就是不说 |
调皮 |
知乎:https://www.zhihu.com/question/66851503 从一棵树转化为另外一棵树,直观的方式是用动态规划,通过这种记忆化搜索减少时间复杂度。由于树是一种递归的数据结构,因此最简单的树的比较算法是递归处理。确切地说,树的最小距离编辑算法的时间复杂度是 O(n^2m(1+logmn)), 我们假设 m 与 n 同阶, 就会变成 O(n^3)。 |
Dads
原始邮件
发件人: Zhilin<notifications@github.com>
收件人: Advanced-Frontend/Daily-Interview-Question<Daily-Interview-Question@noreply.github.com>
抄送: Subscribed<subscribed@noreply.github.com>
发送时间: 2019年7月10日(周三) 18:37
主题: Re: [Advanced-Frontend/Daily-Interview-Question] 第 97 题:React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ,那么 O(n^3) 和 O(n) 是如何计算出来的? (#151)
我知道,但是我就是不说
你真坏
死鬼
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub<#151?email_source=notifications&email_token=AE2P5FJGNTWVJXOEOVPP7DLP6W3YHA5CNFSM4H4TKCU2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZTB2BY#issuecomment-510008583>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AE2P5FMB4TIKAG22GM222J3P6W3YHANCNFSM4H4TKCUQ>.
|
谈一下理解: |
关于O(n^3)怎么计算出来的问题描述原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ,那么 O(n^3) 和 O(n) 是如何计算出来的? ”
倘若这个算法用到别的行业,比如医药行业,肯定是不行的,为什么? React 和 Vue 做的假设是:
如果变化发生在不同层或者同样的元素用户指定了不同的key或者不同元素用户指定同样的key, 但是React 认为, 前端碰到上面的第一种情况概率很小,第二种情况又可以通过提示用户,让用户去解决,因此 基本概念首先大家要有个基本概念。 其实这是一个典型的最小编辑距离的问题,相关算法有很多,比如Git中 leetcode 有原题目, 对于树,我们也是一样的,我们定义三种操作,用来将一棵树转化为另外一棵树:
事实上,从一棵树转化为另外一棵树,我们有很多方式,我们要找到最少的。 直观的方式是用动态规划,通过这种记忆化搜索减少时间复杂度。 算法由于树是一种递归的数据结构,因此最简单的树的比较算法是递归处理。 详细描述这个算法可以写一篇很长的论文,这里不赘述。 确切地说,树的最小距离编辑算法的时间复杂度是 题外话大家如果对数据结构和算法感兴趣,可以关注下我的leetcode题解 |
React 从来没有说过 “React 比原生操作 DOM 快”。React 的基本思维模式是每次有变动就整个重新渲染整个应用。如果没有 Virtual DOM,简单来想就是直接重置 innerHTML。很多人都没有意识到,在一个大型列表所有数据都变了的情况下,重置 innerHTML 其实是一个还算合理的操作... 真正的问题是在 “全部重新渲染” 的思维模式下,即使只有一行数据变了,它也需要重置整个 innerHTML,这时候显然就有大量的浪费。
Virtual DOM render + diff 显然比渲染 html 字符串要慢,但是!它依然是纯 js 层面的计算,比起后面的 DOM 操作来说,依然便宜了太多。可以看到,innerHTML 的总计算量不管是 js 计算还是 DOM 操作都是和整个界面的大小相关,但 Virtual DOM 的计算量里面,只有 js 计算和界面大小相关,DOM 操作是和数据的变动量相关的。前面说了,和 DOM 操作比起来,js 计算是极其便宜的。这才是为什么要有 Virtual DOM:它保证了 1)不管你的数据变化多少,每次重绘的性能都可以接受;2) 你依然可以用类似 innerHTML 的思路去写你的应用。 作者:尤雨溪 |
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。 |
臭弟弟,宁可别给我逮着了 |
你吓到我了 |
diff策略 |
没看懂你们的回答在答什么,原来的O(n^3)是怎样的,然后通过什么策略变成了O(n)的? |
昨晚我就被字节问了,问的很深 |
问题只是问3次方怎么计算,没有说 n 怎么优化的哦 |
话说回来 react 的 diff 应该是 O(2n) 吧,第一次 n 是新树一对一节点对比老树,第二次 n 是应用 patches .... |
原来的 O(n^3) 的 diff 流程是:
|
个人猜想:
vue的更新策略就是:深度优先、同层比较。就是只比较同层级,也就是 O(n) |
海康威视 |
|
火花思维有问到 |
@azl397985856 根据 key 来进行比较,这个过程的复杂度不是 O(k1 * k2) 的吗 (k1, k2 分别为新旧子元素列表长度);即便使用 Map / Hash 优化,也应该是 O(k1 log(k2)),好像也达不到 O(N) 的复杂度 |
打你小屁屁 |
为了降低算法复杂度,React的diff会预设三个限制: 只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级,那么React不会尝试复用他。 两个不同类型的元素会产生出不同的树。如果元素由div变为p,React会销毁div及其子孙节点,并新建p及其子孙节点。 开发者可以通过 key prop来暗示哪些子元素在不同的渲染下能保持稳定。 |
我也被问到了,滴滴 |
O(n^3)是指两棵树diff时:
O(n^3) = O(n) * O(n^2)得出,涉及了跨层级对比计算出的结果。 而React优化后的O(n^2)只做了同级diff,如果同级(位置)diff不同,则删除原节点再重新生成一个新节点,所以时间复杂度是O(n) |
我们知道,两棵树做 diff,复杂度是 O(n^3) 的,因为每个节点都要去和另一棵树的全部节点对比一次,这就是 n 了,如果找到有变化的节点,执行插入、删除、修改也是 n 的复杂度。所有的节点都是这样,再乘以 n,所以是 O(n * n * n) 的复杂度。 |
你说的火花思维是做儿童教育的 |
这个好像偏题了啊 不是楼主问的.. |
No description provided.
The text was updated successfully, but these errors were encountered: