Le 18/09/2012 13:26, Miles Gould a écrit : > On 18/09/12 12:09, Miles Gould wrote: >> I *think* this means that the merge algorithm is >> constant-time in the depth of patches that need merging. > > A minute's extra thought convinces me that I was wrong about that. > Suppose we have > > a-b-c-d-e-f-g > \ > h-i-j-k-l-m > > and want to merge them using pushouts. We must first compose the patches > c-d, ..., f-g and the patches h-i, ..., l-m and then take the pushout of > the two resulting composite patches. So in general, merging n patches > with m patches is O(n + m). But AIUI in Darcs, we have to commute every > patch in one branch past every patch in the other branch, so it's O(nm) > - is this right? > I think it would be O(nm) in the categorical framework too, if finding the pushout is linear in the size of each of the patches (ie the compositions c…g and h…m). I think this more or less follows from the definition of the pushouts.
-- Florent _______________________________________________ darcs-users mailing list darcs-users@darcs.net http://lists.osuosl.org/mailman/listinfo/darcs-users
