Skip to main content

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [jgit-dev] MyersDiffPerformanceTest awfully slow on

On Fri, Sep 17, 2010 at 1:29 AM, Johannes Schindelin
<Johannes.Schindelin@xxxxxx> wrote:
> On Thu, 16 Sep 2010, Shawn O. Pearce wrote:
>> Ideally PatienceDiff will be faster, and we'd be able to only use
>> MyersDiff on really perverse inputs, or drop it altogether.
> MyersDiff is a required fall-back path in PatienceDiff.

True, PatienceDiff needs a fall-back path when there are no more
common unique elements in the region being examined, and the region is
larger than 1 element in length.  But MyersDiff isn't the only
algorithm available to us here.  I might implement a fall-back that
builds up a histogram of the elements by hashing them, and then
looking for the LCS along the least common matches.  That may still
help us to avoid matching around "\t}\n" elements in source code


Back to the top