[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: Daniel Berlin <dan_at_dberlin.org>
Date: 2002-02-11 18:35:11 CET

On Mon, 11 Feb 2002, Mark Benedetto King wrote:

> 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).
Yes.

Remember, however, that skiplists are non-deterministic by default, and
thus, rely on a good random number generator.

Though there are balanced skiplists, with trivial balancing algotithms.

--Dan

---------------------------------------------------------------------
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.