[darcs-users] Replacing the n^2 algorithm.

[Michael Conrad]

On Tuesday, January 11, 2005 5:18 AM, David Roundy wrote:

> The problem isn't an O(N^2) problem--if it were O(N^2) it wouldn't be a
> problem at all.  It is an O(e^N) problem (or perhaps O(N!), which only
> differs by a factor of log(n)).  The conflictor code eliminates this
> exponential behavior.  Whether it can be made bug-free is a separate
> question.

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?

> Your points here really are irrelevant to the exponential behavior, since
> it can just as easily be generated without having a conflict between the
> creation of two files--it's fundamental to how we deal with conflicts.

Well, maybe thats something I misunderstood.  Does the exponential time
happen while darcs decides what files conflict, or while it tries to decide
how to merge them?  or is that the same process?

My suggestion was aiming at "don't let darcs resolve anything, just find
the conflicts, report them, and ask what the user wants to do about it".
Then the idea was that the user could probably tweak either the patch or
the existing directory so that there weren't any conflicts, avoiding the
whole issue.

If the merger patch is the recording of the conflict detection process,
then I guess none of those ideas would help after all.

> As far as the idea (#6) of making a special patch annotation/patch type
for
> patch resolutions, I don't think it's a good one.  There are too many
> special cases, and I think it's best to just use the existing darcs patch
> types to describe the resolution.

Well, to be a bit more specific about my reason, currently in the duplicate
file issue all files in question get recorded multiple times. Once
originally, numerous times during the merger, and then one last time after
the user resolves and records the resolution.  I was just thinking along
the typical lines of using less space.

-Mike