4 ms·
Trees are a special case of graphs in general, which aren't necessarily even NP-complete. In fact, if trees couldn't be diffed things like React would have ser
by Etzos 10y ago
Trees are a special case of graphs in general, which aren't necessarily even NP-complete.
In fact, if trees couldn't be diffed things like React would have serious speed concerns, or more realistically wouldn't even exist in the first place.
- schoen 10y agoYeah, a lot of important things in graphs are not all that hard, like most graph shortest path problems taking (small) polynomial time: https://en.wikipedia.org/wiki/Shortest_path_problem https://en.wikipedia.org/wiki/Shortest_path_problem
- amelius 10y agoReact is not optimal, or it would require O(N^3) time at least. Think for example of a linear structure like a listbox, and then consider that a perfect diff requires an algorithm like Smith-Waterman, which is O(N^3). (Perhaps faster algorithms exist, but they are probably not really significantly faster).
- Etzos 10y agoI certainly wasn't commenting on the preciseness of React's diffing (and how they're able to reduce it from O(n) to O(n^3) by ignoring things). I was merely pointing out that it's possible to diff trees in polynomial time. Edit: Just to clarity, I'm also not saying O(n^3) isn't slow compared to React's O(n), just that it's potentially a lot faster than NP.