Anyone know of papers or articles on the VDOM patch algorithm in React based on keys? That is, to make patching reordered lists fast. I've searched for material but nothing so far. I have a few napkin notes on a functional implementation that I'd like to compare to prior art.
-
Show this thread
-
Replying to @owickstrom @bodil
Check for shortest-edit path algorithms. Idk which algos react uses but Myers diff + patience diff optimizations should get you most of the way there.
2 replies 0 retweets 1 like -
Replying to @yoshuawuyts @bodil
Yeah, I was looking a bit at those, not sure how they would be applicable to the VDOM case, but it might be worthwhile digging further. The "graph of edits" and shortest path is interesting.
1 reply 0 retweets 0 likes -
Also not sure how that works with trees? I've only seen examples on strings.
1 reply 0 retweets 0 likes -
Replying to @owickstrom @yoshuawuyts
I imagine they help when patching lists of children.
1 reply 0 retweets 2 likes -
Replying to @bodil @yoshuawuyts
Yeah, might just be recursive application of the same thing. But the edit graph approach I've seen doesn't handle reordering, as done in React with keys. I think the basic prepend case would work, but not general reordering.
1 reply 0 retweets 0 likes -
Replying to @owickstrom @bodil
With Myers you get reordering of a list of nodes, similar to how git supports diffs beyond just append/prepend. It only applies to siblings in lists, but in practice that's all the only case where reordering is needed. Indeed done by recursing down.
2 replies 0 retweets 2 likes -
Myers solves LCS problem, reordering children nodes with unique keys is a LIS problem.
1 reply 0 retweets 1 like -
Could you say more? I don't know these acronyms.
2 replies 0 retweets 0 likes -
Replying to @yoshuawuyts @localvoid and
Ah okay: LIS = longest increasing subsequence. In an earlier Tweet I mentioned using Patience Diff as an optimization for Myers which is an LIS algo. You need both tho, and patience doesn't work without Myers (or similar), so I recommend to start with Myers.
1 reply 0 retweets 1 like
(Happy to be educated if there are more efficient versions of either of these algorithms! Myers is *old*, haha)
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.