Re: [dev] situ — change files in situ

From: Strake <strake888_AT_gmail.com>
Date: Fri, 13 Apr 2012 11:50:56 -0500

On 13/04/2012, Connor Lane Smith <cls_AT_lubutu.com> wrote:
> On 13 April 2012 16:37, Strake <strake888_AT_gmail.com> wrote:
>> True, if we trim the start and finish lazily
>
> That depends on the diff format. diff -e, for example, could work well.

I meant to trim pre-diff, so it would be quadratic in a lesser argument.

>> but worst-case diff
>> algorithm space usage is worse — quadratic, if I'm not mistaken.
>
> That's true. Although, diff is worst-case quadratic in the number of
> lines, not bytes.

True for line-by-line diff, e.g. Unix diff, though the algorithm is
more general.

> And the fact is the worst-case can be avoided: we
> don't really *need* the longest common subsequence, only an
> approximation to it. If we exceed some threshold we can simply
> 'plump'.

You mean, to terminate the subsequence, and start afresh?

> To be clear, I don't mean to dismiss either existing situ, this would
> just be nice to have as well.

Noted.

Cheers,
strake
Received on Fri Apr 13 2012 - 18:50:56 CEST