search

chbrown / rfc6902

Complete implementation of RFC6902 in TypeScript
https://chbrown.github.io/rfc6902/
316 stars 39 forks source link

Using dp rather than recursion for better performance #88

Open supermeng opened 2 years ago

supermeng commented 2 years ago

Cause the performance of current diffArrays is so poor, even a 2000 * 2000 scale would cost too much memory and cpu, and can't get result in time, how about using dynamic programming to optimize it

supermeng commented 2 years ago

Solve https://github.com/chbrown/rfc6902/issues/72 together

steida commented 2 years ago

@chbrown Are you interested in this PR? Thank you

chbrown commented 2 years ago

@steida Yes, just been busy. And, I appreciate the contribution, but it's a bit off-putting when a PR misrepresents what it's doing; like, the code currently implements dynamic programming, which the comment for diffArrays even calls out by name.

DP and recursion are orthogonal. I do think a loop is the better way. Yes, it works, but the author's misrepresentation doesn't give me a whole lot of faith that it's correct, so I want to go over it closely before I merge it. It's pretty gnarly code — both mine and the PR — so it's tricky to review.

supermeng commented 1 year ago

with all due respect, the old implementation is just a fake DP, the function recursion call like DP, but the alternatives did not track the struct correctly

steida commented 1 year ago

@supermeng Hi, I am looking for a better algorithm for Evolu https://github.com/evoluhq/evolu/blob/main/packages/evolu/src/query.ts#L50

My use case is simpler because all I need to compare is an array with DB rows (shallow objects). Can you point me to some DP resources? Thank you very much!

supermeng commented 1 year ago

@supermeng Hi, I am looking for a better algorithm for Evolu https://github.com/evoluhq/evolu/blob/main/packages/evolu/src/query.ts#L50

My use case is simpler because all I need to compare is an array with DB rows (shallow objects). Can you point me to some DP resources? Thank you very much!

@steida Hi, the main point of array diff it to match the point between i in array1 and j in array2, if i and j is the point, the (i, j) problem could be reduce to (i-1, j-1), if not could be (i-1,j) or (i, j-1), so the DP recursive: F(n)(m) = min(F(n-1)(m), F(n)(m-1), F(n-1, m-1)) + 1; and using a memo to track if (i, j) is used to be compared for array diff.