On Mon, Feb 11, 2002 at 12:35:11PM -0500, Daniel Berlin wrote:
> 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
>
This may be premature optimization; maybe we even *don't want* them
balanced! I'm thinking that old versions are probably accessed less
frequently than newer versions, for example. If we had good reference
pattern statistics, we could probably come up with an even more exciting
datastructure that plays nicer with space (maybe an LRU-harvested
skip-list, or something).
--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