Why remove O (nlogn) algorithm?

[yisar]

I see that the new version has become o (n) algorithm. Why?

In the past, I always thought that the advantage of Petit is that it uses the algorithm of the longest common subsequence, why to remove it?

What is the trade-off, or is there any benchmark for you to do so?

[yelouafi]

It's true that I started this lib to benchmark the O(ND) algoroithm in vdom diffing. But turns out it doesn't play a big rule in JS frontend (as long as you use a good enough algorithm). A single VM deoptimizaton, or a relayout can outwieght an efficient algorithm by several orders of magnitude.

Besides O(ND) doesn't handle moves very well, and we'd have to account for the worst case where the sequences are totally different. In the old implementation it was handled by switching to an alternative algorithm. This adds in bundle size without concrete benefit in countrepart. The new alogrithm is much shorter and good enough for its use case. I doubt library users would notice any difference but if you spot some performance degradations you can file an issue.

Note: the new algorithm it's not O(N). It'd be great if so but that's impossible. Also the old algorithm was O(ND) where D was the distance between the 2 sequences.

[yisar]

the new algorithm it's not O(N). It'd be great if so but that's impossible. Also the old algorithm was O(ND) where D was the distance between the 2 sequences.

Thank you for your correction. Let's keep waiting.