[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Whither delta combiner

From: Mark Benedetto King <bking_at_answerfriend.com>
Date: 2002-02-11 16:14:30 CET

On Sat, Feb 09, 2002 at 06:15:48PM -0500, Daniel Berlin wrote:
> On 9 Feb 2002, Greg Hudson wrote:
>
> > On Fri, 2002-02-08 at 23:29, Karl Fogel wrote:
> > > Both proposals trade delta space for faster retrieval of old
> > > revisions; haven't done a formal proof, but I'm pretty sure both
> > > methods end up being exactly the same tradeoff, and I think it's about
> > > the same as the skiplist tradeoff, too. (I haven't thought as much
> > > about the skiplists, so this is just an off-the-cuff reaction.)

One HUGE win about skip lists that I don't think anyone has mentioned
is that you don't have to balance them. "always append to end" is the
of the pathological worst-cases of a binary tree, and less naive tree
implementations tend to be buggy. Skip Lists, OTOH, are relatively
easy to implement (and, as a bonus, append is a very cheap operation).

--ben

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Oct 21 14:37:06 2006

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.