Geek asks and answers

What is the fastest (insertion speed) to achieve a priority set of arrays in .Net?

I write a specific priority queue. Its structure should be something like the following:

Priority(<int>)    Data(List<Object>)
1                  a, b, g, h
3                  c, d, j
4                  k
10                 e, f, i

I need to be able to efficiently find if a list exists for a given priority; if not, create a list and add a message, otherwise add a message to the existing list.

I wrote a red-black tree, but this seems redundant for this and may not be the fastest solution. It also has the disadvantage that you cannot easily capture messages by priority, which I need to do as soon as the recording is complete.

I was thinking about the Dictionary, but if I'm not mistaken, it has no easy way to say "if the __ key exists, give me its value, otherwise give me null." Or am I missing something?

EDIT

My current implementation is to have 32 fixed lists. An applicable list is added and the corresponding bit is set to the 32-bit flag. I use the De Bruijn algorithm to get LSB. This is effective, but adds another complexity that I want to facilitate.

+3
source share
3 answers

Perhaps you should use Dictionary<int,List<object>>

public void Add(int priority,object data)
{
    if(dictionary.ContainsKey(priority))
       dictionary[priority].Add(data);
    else
       dictionary.Add(priority,new List<object>{data});
}
+3
source

A SortedDictionary will populate the job. Just use TryGetValue () to conditionally find the list.

+3
source

Hm, what happened with Dictionaryas the main container? You get the average access / input time O (1), not O (log n) with rb trees. Just wrap Dictionaryaccording to your needs, for example:

internal public class PriorityQueue<TValue> 
{
    private Dictionary<int, List<TValue>> mDict;

    // only Add, TryGetValue shown...
    public void Add(int pPriority, TValue pInput) 
    {
        List<TValue> tTmp;
        if (mDict.TryGetValue(pPriority, tTmp)) 
        {
            tTmp.Add(pInput);
        } 
        else 
        {
            mDict.Add(pPriority, new List<TValue>{ pInput });
        }
    }

    public bool TryGetValue(int pPriority, out List<TValue>) 
    {
        // obvious...
    }
}
+3
source

More articles:


All Articles