Dictionary Problem solved..but is it a good solution?

[David H]

I'm implementing an application that needs to keep track of a
prioritized list of items. To do this, am using a dictonary along the
lines of :

Dictonary<int,string> myList =new Dictonary<int, string>()

The key represents the priority. The problem? I need for the
dictionary to allow me to add new items of the same priority and
simply bump down the existing item. For example:

myList.Add(1,"B");
myList.Add(2,"C");
myList.Add(3,"D");

A call to correct the list and add a (myList.Add(1,"A") will fail with
an exception.
My solution has been to wrap the dictionary in a class and create a
custom add method for the class that will re-order the dictionary.

The result is
myCustomList.Add(1,"B");
myCustomList.Add(2,"C");
myCustomList.Add(3,"D");
//No exception...The list is re-ordered and expanded so that A is now
1, and b is 2 ext..
myCustomList,Add(1,"A");


So I've solved the problem, but I can't help but wonder if I'm doing
more work than I need to. Is there a better way of handling a
situation like this?

Any suggestions/advice would be appreciated.

 

[Peter Morris]

What about using the PriorityQueue<T> class?

 

[Brian Gideon]

What about using the PriorityQueue<T> class?

I don't think that class exists in the BCL. But, yeah, a priority
queue sounds like the best option.

 

[Peter Morris]

I just noticed, it's internal.

 

[Peter Morris]

I'd write a class wrapper around

Dictionary<int, List<T>>

something like this (written in email client)

public class Blah<T>
{
private Dictionary<int, List<T>> Queue = new Dictionary<int, List<T>>();

public void Push(int priority, T item)
{
List<T> list;
if (!Queue.TryGetValue(priority, out list))
{
list = new List<T>();
Queue[priority] = list;
}
}

public T Pop()
{
T result = default(T);

int? highestPriority = null;
foreach (KeyValuePair<int, List<T>> kvp in Queue)
if (!highestPriority.HasValue || kvp.Key <
highestPriority.Value)
highestPriority = kvp.Key;

if (highestPriority.HasValue)
{
List<T> list = Queue[highestPriority.Value];
result = list[0];
result.RemoveAt(0);
if (list.Count == 0)
Queue.Remove(highestPriority.Value);
}
return result;
}
}


Not thread safe, probably better ways of doing it if you spend more than a
few seconds thinking it through (like storing an ordered list of priorities
*if* there will be many different priority numbers, or using an object as
the priority and providing a comparer, etc), and it probably wont compile
either. It's merely an illustration


Pete

 

[KH]

Why not just use a regular List<T>? It has Insert(int, T) method to insert
items in a specific place which will move the others "down" in the order,
Count property tells you how many are in the set and each items index
indicates its priority.

Another option might be to make your dictionary a Dictionary<int, Stack<V>>
-- so when an item comes up with the same priority as an existing one you
push it onto the stack and effectively moves the other to lower priority.

Finally if you wanted Queue-like behavior you could write your own Queue
class with an Insert() method -- you could probably inherit from List<T> and
just keep a pointer to the next item.

HTH

 

[Pavel Minaev]

I'm implementing an application that needs to keep track of a
prioritized list of items. To do this, am using a dictonary along the
lines of :

Dictonary<int,string>  myList =new Dictonary<int, string>()

The key represents the priority. The problem? I need for the
dictionary to allow me to add new items of the same priority and
simply bump down the existing item. For example:

myList.Add(1,"B");
myList.Add(2,"C");
myList.Add(3,"D");

A call to correct the list and add a (myList.Add(1,"A") will fail with
an exception.
My solution has been to wrap the dictionary in a class and create a
custom add method for the class that will re-order the dictionary.

The result is
myCustomList.Add(1,"B");
myCustomList.Add(2,"C");
myCustomList.Add(3,"D");
//No exception...The list is re-ordered and expanded so that A is now
1, and b is 2 ext..
myCustomList,Add(1,"A");

So  I've solved the problem, but I can't help but wonder if I'm doing
more work than I need to. Is there a better way of handling a
situation like this?

Any suggestions/advice would be appreciated.

Unless you need to retrieve items by a specific priority value (and
not simply enumerate them in order of priority), it would seem that a
plain sorted List would do better here, performance-wise. If I
understood your description correctly, on every insert, you check
whether an item with such key exists, and if it does not, you remove
it and reinsert it into the dictionary with new priority (where insert
is recursive - so you again check if an item exists, etc). This means
that you do a lot of lookups and updates for a simple operation.

With List, you can find the position for the new item in the list by
binary search, and insert it there. After that, you iterate from that
position down to the end of the list. On each step, you check whether
the priority of current item is equal to the priority of the previous
item, and if so, increment it by one (and if not, you can just break
out of the loop). Something like this:

class PriorityQueue
{
private List<KeyValuePair<int, string>> list; // this is always
sorted by priority at any given moment of time

public void Add(string item, int priority)
{
var pair = new KeyValuePair<int, string>(item, priority);
int index = list.BinarySearch(pair);
if (index < 0) index = ~index;
list.Insert(index, pair);
for (int i = index + 1; i < list.Count; ++i)
{
if (list.Key == priority)
priority = ++list.Key;
else
break;
}
}

Even better would be to use a balanced tree to reduce the cost of
inserts; but you'd have to roll out your own, which is probably too
much of a hassle unless you have stringent performance requirements
there.

 

[Brian Gideon]

Even better would be to use a balanced tree to reduce the cost of
inserts; but you'd have to roll out your own, which is probably too
much of a hassle unless you have stringent performance requirements
there.

Even better still would be to use a skip list. You get roughly the
same insert, delete, and search performance as a balanced BST, but
since it has definitively placed end nodes (head and tail) the
operations on those nodes are constant time. That is an attractive
property for priority queues since the dequeue operation always
removes from the head or tail (depending on how you orient the
queue). Not to mention that they can be tuned to use less memory than
most balanced BSTs and are *much* simpler to implement.