[darcs-users] Replacing the n^2 algorithm.
aj at azure.humbug.org.au
Fri Jan 14 04:57:59 UTC 2005
Michael Conrad wrote:
> Aah, I'd been reading it wrong. Actually, N^2 could also be a problem,
> depending on what N was. (i.e. number of conflicts vs. number of patch
> units between conflicting units, etc) Anyway, yes e^N is much worse,
> and I'm assuming now that N is number of conflicts?
N is the number of conflicting patches.
Say you have A1, A2, A3, A4, A5, etc all conflicting, and you pull them
one at a time, in order.
Your initial repository is just A1, it's size is 1.
Your second repository is A1 + M(A1,A2), it's size is 1+(1+1).
Your third repository is A1 + M(A1,A2) + M(M(A1,A2),M(A1,A3)), it's size
Your N+1 th repository is thus made up of the N patches that made up
your N th repository, and an additionally patch which conflicts with
every other patch in the repository, which is of the form:
M( p_n-1, M( p_n-2, M( ... M( p_1, p_n ) ) ) ) )
But p_n-1 + ... + p_1 is what made up the N-1'th repository, so that
patch alone is the size of the previous repository + 1 (for p_n).
So if S_i is the size of the ith repository, S_1=1, S_(i+1)=2(S_i)+1;
and hence S_i=2^(i)-1. (Check: S_1=2^1-1=1; S_i+1=2(2^i)-1)+1=2^(i+1)-1)
That complexity is due to the representation of mergers -- the fact that
p_n-1 above isn't just a "hunk ./foo 1234" patch, but is itself a merger
of the preceeding patches.
More information about the darcs-users