On Thu, Mar 26, 2009 at 09:41:30AM +0000, Eric Kow wrote:
>
> I have a potentially silly question: is it fair to characterise
> darcs-style merging in the absence of conflicts as being O(n * m) time,
> with n and m being the number of uncommon patches on each side?
I think it's a reasonable approximation.
If you have
As Bs + As Cs
then you need to do (#Bs * #Cs) commutes.
Commutes are more-or-less constant time. There are some examples where
that isn't true, e.g. commuting a replace patch with a hunk (where you
need to see if the replace touches anything anywhere in the hunk).
If you have the pathological case
Bs' As' + Cs' As''
then you need to do (#As * #Bs + #As * #Cs + #Bs * #Cs) commutes.
> informal way of arriving at this characterisation of things is that we
> can say the cost of commutation is constant (wrt # of patches, provided
> no conflicts), and that the only work you have to do is to commute each
> one of m patches past one of the m patches. Is that the correct way of
> looking at things?
Yes.
Thanks
Ian
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
