Re: Efficient Data Structures

Tech-Archive recommends: Fix windows errors by optimizing your registry

Hi,
I agree with the others that the Red/Black tree should be easy to fix, and the SortedList will probably do what you want, too.

But you could also try my favorite data structure, the SkipList. There is a c# implementation on CodeProject here: http://www.codeproject.com/csharp/SkipList1.asp.

The article includes benchmarks against a SortedList, and SkipList beats it handily. SkipList is also much simpler than a Red/Black tree, and should give better average performance. You'll have to test this to be sure, though.

Gabe

Curious wrote:

I am searching for a data structure that stores key-value pairs in it.
This data structure is to hold large amounts of key-value pairs, and so
needs to be efficient both in insertion and deletion.

Does anybody know of ready data structures that can be freely used
under the .Net framwork.



Also:

I forgot to mention, that the data needs to be maintained sorted.
When removing the data, the minimum key with its data is to be removed.


You won't *necessarily* get great efficiency on both insertion and removal. But given your description so far it sounds as if you can - I would try a SortedList. The insertion uses .Add(object key, object value) - which *should* be efficient, at least if the key elements arrive in anything like random order. (Test it!) You can remove elements either with .Remove(object key) or .RemoveAt(int index) - index being 0 in your case of removing the element with least key. Either of these *should* be quite efficient (O(log n) at worst) *if* the list is internally maintained sorted as per the documentation. (Again, test it!)

HTH,
-rick-

.

Relevant Pages

  • Re: Efficient Data Structures
    ... This data structure is to hold large amounts of key-value pairs, and so needs to be efficient both in insertion and deletion. ... When removing the data, the minimum key with its data is to be removed. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Intervals tree
    ... I'm looking for a data structure to handle intervals (numeric range ... deleted and queries about intersecation are required. ... implementation seems not to allow insertion and deletion. ...
    (comp.graphics.algorithms)
  • Re: lxml/ElementTree and .tail
    ... Stefan Behnel wrote: ... What other API do you know where removing an element from a data structure ...
    (comp.lang.python)
  • Re: Efficient Data Structures
    ... > This data structure is to hold large amounts of key-value pairs, ... > needs to be efficient both in insertion and deletion. ...
    (microsoft.public.dotnet.languages.csharp)