[PATCH] auto rename: best matches and speed improvement UPDATE4

[Matt Mackall]

On Sat, 2008-08-16 at 01:48 +0200, Herbert Griebel wrote:
> # HG changeset patch
> # User Herbert Griebel <herbertg at gmx.at>
> # Date 1218843942 -7200
> # Node ID 6cf73b7c3671f0737e25c72d45fa3ca805426df6
> # Parent  438e02b4be73ffd80d4a6cc45b7c9273d6b26604
> auto rename: best matches and speed improvement
> 
> The auto rename feature of addremove did not rename to the best match.
> The old implementation looped over "added files" and selected the best
> match for each individually. The next "added file" could also have its
> best match with the same removed file, but which is far lower than the
> one before. Therefore the last "added file" wins which may not be the
> best.
> The new implementation fixes this. The rename list is also sorted in
> reverse order to make it easier to find the wrong matches with low
> similarity. For speed improvements the loops are dynamically
> interchanged which can speed up the matching considerably.
> There is also a very rough estimation of the matching time, and
> output has been enhanced to give the user feedback about the
> progress.

Thanks for looking into this, Herbert.

First off, this will want a test case.

Second, I get the impression that the time complexity here is going from
O(n) to O(n**2), is that right?

-- 
Mathematics is the supreme nostalgia of our time.