Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposed significant optimization for common cases #88

Open
epatey opened this issue Mar 11, 2018 · 4 comments
Open

Proposed significant optimization for common cases #88

epatey opened this issue Mar 11, 2018 · 4 comments

Comments

@epatey
Copy link

epatey commented Mar 11, 2018

Great work with Dwifft. Thanks for it.

One challenge with the LCS algorithm is that it is O(m*n) in both CPU and memory consumption. Though this isn't a problem in practice when the size of the arrays is moderate, it becomes a problem when the arrays are large.

Anything that can be done to reduce the size of the arrays passed to the LCS algorithm has very beneficial results.

This approach, which I've used in the past in another language, is to essentially trim off the matching prefixes and suffixes from the arrays passing only the "middle" of the array to the LCS algorithm.

Of course, if there is a change at both the head and tail of the array, this optimization has no benefit. In the common case, though, the benefit is huge.

Based on the guidelines, I thought it would be good to discuss the idea before opening a PR. Nevertheless, it may be easiest to just see the code.

In my previous implementation, I also added change beyond what I've proposed here to pick an upper bound on m*n work factor. When that limit is exceeded, a reloadData is really the best approach.

@jflinter
Copy link
Owner

Hey @epatey,
Thanks for opening this. This seems like a great idea to me, and I'd be open to merging a PR that implemented it. I do have some changes I'd probably want to make to the code in the diff you linked, but nothing systematic - if you send me a PR I'll give it a thorough review.
Have a great weekend!

@epatey
Copy link
Author

epatey commented Mar 19, 2018

#89

@MauriceArikoglu
Copy link

@jflinter @epatey How is the status on this one?

@jeanfw
Copy link

jeanfw commented Aug 17, 2018

Hi, this is interesting, thanks for making Dwifft!

We have another (presumably) common case where our list of items is stably sorted. It doesn't seem Dwifft is taking advantage of this to optimise performance.

@jflinter Is there a way to tell Dwifft that the values are already sorted, which should result in a much less complex diff?

@epatey is this something that could be of interest to further improve the optimisations you're working on?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants