Re: [jgit-dev] MyersDiffPerformanceTest awfully slow on build.eclipse.or

[Shawn Pearce <spearce@xxxxxxxxxxx>]

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
files.

-- 
Shawn.