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