5 ms·
> O(n^2) algorithm gets noticeably slow. What algorithm? If that's about diff/reconciliation of DOM/VDOM then it is worse than that - O(n^3).
by c-smile 7y ago
> O(n^2) algorithm gets noticeably slow.
What algorithm? If that's about diff/reconciliation of DOM/VDOM then it is worse than that - O(n^3).
- forrestthewoods 7y agoCan you point me to a good resource on what the n^3 process is? It’s not intuitive to me why it’s so, ahem, complex. Thanks! :)
- fyp 7y agoI think he's way off on the complexity. He might be confusing it with text diffs where you need to find the longest common subsequence for the shortest possible diff but that is still O(N^2). If you are just diffing a list with unique ids (like react child nodes are, with their required key prop), it's just a set intersection which is linear. I can see it being a bit more complex if you need to track how nodes move across different parents. But it seems like react doesn't handle this: https://github.com/facebook/react/issues/3965# https://github.com/facebook/react/issues/3965#
- deleted 7y ago[deleted]
- baddox 7y agoThe O(n^3) is to compute the minimum set of operations to transform one VDOM tree into another VDOM tree. React apparently uses simple heuristics to generate a diff in linear time. https://reactjs.org/docs/reconciliation.html https://reactjs.org/docs/reconciliation.html
- ex3ndr 7y agoVDOM is O(n).