Missing Tomes of Data Structures

[jehugaleahsa]

Hello:

I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists. I am currently approaching the
completion of a data structure library I am implementing.

I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.

In addition, there is a data structure called a forward-balancing B-
Tree that lets implementors lock sub-trees instead of the entire tree
itself. It does this by ensuring the tree is balanced ahead of time so
it can lock as little as possible.

Any ideas?

 

[Peter Duniho]

I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists. I am currently approaching the
completion of a data structure library I am implementing.

I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.

In addition, there is a data structure called a forward-balancing B-
Tree that lets implementors lock sub-trees instead of the entire tree
itself. It does this by ensuring the tree is balanced ahead of time so
it can lock as little as possible.

Any ideas?

Google?

I admit, I had not heard of either. Google provides nothing relevant
when using "forward-balancing b-tree" as the search time, so I'm
wondering if you got the term right. You say one exists; why do you
think it does? Why does it appear that there's no one else on the
Internet who's ever heard of it?

As far as the skip-list goes, as near as I can tell from the
descriptions of the algorithm (including Pugh's own paper where he
published it), randomization is a key element of the data structure.
When you write "deterministic", what exactly is it that you want to be
deterministic about the skip-list? And what sort of trouble are you
having in applying that goal to your current implementation?

For both of your questions above, it's almost as if you are asking for
help implementing something that doesn't (or can't) exist. If that's
actually what's going on, then obviously you won't get an answer. If
it's not what's going on, then at the very least there seems to be some
ambiguities and/or inaccuracies in your question that you might want to
explore, to see if you can rephrase the question in a way more likely to
get the help you need.

Pete

 

[Peter Duniho]

I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists. I am currently approaching the
completion of a data structure library I am implementing.

I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.

Oh, and reading further in Pugh's paper, I'm not really clear on why a
data structure library needs a skip list implementation.

By his own analysis, the value in the skip list data structure is
primarily in ease of implementation. So it's apparently worth knowing
about if you are implementing the structure from scratch. But a data
structure library should have instead an optimized b-tree data
structure, obviating any need for a skip list.

Just a thought.

Pete

 

[Michael Starberg]

Hello:

I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists.
Why?

I am currently approaching the
completion of a data structure library I am implementing.

I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.

Maybe because 'skiplist' is a funny programming-task
to hand out to students. Not so fun to sit and correct them
when code was still handwritten or printed on paper. *S*

I say this with no disrespect nor laughter.
I've written a skiplist in c, and that was fun.
I learned a lot about linked list.

In addition, there is a data structure called a forward-balancing B-
Tree that lets implementors lock sub-trees instead of the entire tree
itself. It does this by ensuring the tree is balanced ahead of time so
it can lock as little as possible.

Woo...Now you are digging deep
Are you talking about a B-Tree, or a Binary-Tree?

And why do this is C#?
This is what I would do

var my12345Thingy = thingies.Single(t => t.ID == 12345);

That might not look as if it is what you want,
but with plinq, and give the code a few years,
I am sure my code above will outperform
anything you can 'skip' in pure asm

Are you sure you are in the right forum?

Any ideas?

Do you feeling lucky, punk. Well do ya'?
- Michael Starberg

 

[Michael Starberg]

(e-mail address removed) wrote:

I admit, I had not heard of either. Google provides nothing relevant when
using "forward-balancing b-tree" as the search time, so I'm wondering if
you got the term right. You say one exists; why do you think it does?
Why does it appear that there's no one else on the Internet who's ever
heard of it?

I think he means a BTree, not a binary-tree.
BTrees are always balanced, and pretty cool.

As far as the skip-list goes, as near as I can tell from the descriptions
of the algorithm (including Pugh's own paper where he published it),
randomization is a key element of the data structure. When you write
"deterministic", what exactly is it that you want to be deterministic
about the skip-list? And what sort of trouble are you having in applying
that goal to your current implementation?

Haha. Nice catch. A non-destermistic skiplist
is what QA-people would rename a frekkin bug

For both of your questions above, it's almost as if you are asking for
help implementing something that doesn't (or can't) exist. If that's
actually what's going on, then obviously you won't get an answer. If it's
not what's going on, then at the very least there seems to be some
ambiguities and/or inaccuracies in your question that you might want to
explore, to see if you can rephrase the question in a way more likely to
get the help you need.

Pete, note how your are spanking someone
who obviously wants her homework done for her.

Pete

- Mike

 

[Michael Starberg]

(e-mail address removed) wrote:

Oh, and reading further in Pugh's paper, I'm not really clear on why a
data structure library needs a skip list implementation.

Did I say I respect your stamina and patience, Pete?
I think you have earned your MVP.

Jon Skeet: If atleast two MCPD thinks someone deserves the 'i aMVery
imPaired' status,
how do one promote one with such an honor. I know, poke skeet and let stuff
happen..

Mr. Duniho so deserve it.

- Michael Starberg