search

yudai / golcs

Go Longest Common Subsequence
MIT License
21 stars 5 forks source link

Pathologically bad performance with long input #1

Closed pteichman closed 7 years ago

pteichman commented 7 years ago

This is also documented somewhat over at gojsondiff (https://github.com/yudai/gojsondiff/issues/9 where maybe some API changes can help), but the core issue is here in golcs.

It's possible to construct strings of around 10000 bytes (on my machine at least) that cause lcs.Length() to run indefinitely. I've added a test case over here: https://github.com/pteichman/golcs/tree/infinite-hang

Is your sense that this could be improved with a different algorithm in golcs, or should the API be extended to allow cancellation if a deadline is exceeded (using, say, context.Context)?

pteichman commented 7 years ago

Once I took a look at the code it was clear that this is an O(n*m) problem and so maybe not overtly fixable, but I think the suggestion to add cancellation to the API still makes sense.

yudai commented 7 years ago

Finally I got some time to fix this issue. Thanks for the report and your patient.