3 ms·

Can 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 ago
  I 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 ago
    The 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