Closed rizrmd closed 8 months ago
Interesting attempt. Maybe try with return true
and validate the output instead. return false
makes the algorithm degenerate to quadratic. return true
should be linear but gives an incorrect output with a smaller difference.
Another option that should be possible with Myers' algorithm is to set a maximum length for the diff (i.e. minimum length for the LCS) beyond which the algorithm would not try to find a match. Not sure if this is part of the public API of fast-myers-diff
yet, but you can already try it with @edit-distance/myers-1986
which I wrote and tell us if it would help you if fast-myers-diff
implemented the same as part of the public API.
A last option is to run such long computations in a worker thread.
After tinkering with fast-myers-diff
internal, i found that h_loop:
method is called to generate the generators. I just put my own should_break()
function there:
if should_break()
then it just return 0.
I don't know if this is the correct approach, but my timeout returns exactly 300ms. Hence, the job is done... I think.
Of course the resulting diff is unusable. So the correct action is to throw an Error when timeout is reached.
@rizrmd Wait, how can any of the suggested solutions possibly work given the computation is synchronous?
@rizrmd Does state.should_break()
in your example do something akin to return Date.now() - state.start >= timeout
perhaps?
yes. But I use performance.now() instead of Date.now()
Most of the time
fast-myers-diff
works fast, great job!Sometimes, calculating patch for unoptimal input takes forever. I'm wondering if we can put a timeout, e.g. maximum 300ms, if calcPatch takes more than that it will throw an exception
I tried naive implementation, but it does not work:
result_diff still run even
time_out === true
.What do you think ?