Skiplist questions
ggeurts
supports indexed lookups (as provided by IList<T>) in a sorted
collection. Besides the regular .NET ListDictionary<TKey,TValue> I had
not been able to find much else, until I read about indexed skip lists
on Wikipedia.
Are there any plans to support this in NGenerics? As far as I can tell
the current SkipList implementation does not (yet) support indexed
operations. It also seems to be rather memory hungry when both TKey
and TValue are value types.
Regards,
Gerke Geurts.
ggeurts
> .. It also seems to be rather memory hungry when both TKey and TValue are value types. ...
>
Please ignore the above statement. I should have double-checked the
SkipListNode implementation.
Simon
Yes this is possible and you should add a feature request here
http://code.google.com/p/ngenerics/issues/list
or better yet submit a patch :)
but what do u need an index for on a skip list?
Simon Cropp
From what I can tell adding an index to skiplist is possible if we
take a small hit on the add funtionality. What do u think since this
is one of your original classes?
rhanekom
Do me a favor and send me the link to what you read on Wikipedia so
that I can have some context. A couple of questions :
>> I have just been looking into which data structure to use that
>> supports indexed lookups (as provided by IList<T>) in a sorted
>> collection.
What is your definition of an indexed collection here? Should the
index value signify the order the items were added, or the order the
items are stored in the collection?
>> (as provided by IList<T>) in a sorted collection.
Does SortedList not match your requirements? Tell us a little about
your scenario, i.e. what you need, whether you're doing many reads,
many writes, or a combination of the two. Do you need to look up
items by key on top of referencing them by an integer index?
>> It also seems to be rather memory hungry when both TKey
>> and TValue are value types.
I did see your follow up post on this, but I'm still interested in
this statement. Note that a Skip List *is* a memory hungry data
structure - it works by duplicating the items you add in several
linked lists.
Cheers,
Riaan
Simon Cropp
Riaan Hanekom
Gerke, I'm still interested in your scenario so do send some details.
Riaan