3

SortedDictionaryを使用して優先キューメカニズムを実装しようとしていますが、現在の実装に関する提案を取得したいと思います。

私の実装は次のとおりです。

public class PriorityQueue
{
    private Object lockObj;
    private SortedDictionary<PQMsgPriority, Queue<PQMessage>> messageDictionary; 

    public PriorityQueue()
    {
        lockObj = new object();
        messageDictionary = new SortedDictionary<PQMsgPriority, Queue<PQMessage>>();
    }

    public void Enqueue(PQMessage item)
    {
        lock (lockObj)
        {
            if(item != null && item.MsgPriority == PQMsgPriority.None)
            {
                if (messageDictionary.ContainsKey(item.MsgPriority))
                {
                    Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
                    dataList.Enqueue(item);
                    messageDictionary[item.MsgPriority] = dataList;
                }
                else
                {
                    Queue<PQMessage> dataList = new Queue<PQMessage>();
                    dataList.Enqueue(item);
                    messageDictionary.Add(item.MsgPriority, dataList);
                }
            }
        }
    }

    public PQMessage Dequeue()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;
            PQMsgPriority deleteKey = PQMsgPriority.None;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Dequeue();
                messageDictionary[item.Key] = dataList;

                //If there is no more elements remaining in the list, set a flag (deleteKey) for deleting the key
                if (dataList.Count == 0) 
                    deleteKey = item.Key;

                break;
            }

            //If the deleteKey flag is set, delete the key from the dictionary
            if (deleteKey != PQMsgPriority.None)
                messageDictionary.Remove(deleteKey);

            return messageData;
        }
    }

    public int Count()
    {
        lock (lockObj)
        {
            return messageDictionary.Count;
        }
    }

    public PQMessage Peek()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Peek();
                break;
            }

            return messageData;
        }
    }
}

public enum PQMsgPriority
{
    High = 0,
    Medium = 1,
    Low = 2,
    None = 3
}

public class PQMessage
{
    private PQMsgPriority msgPriority;
    private Object message;

    #region Properties
    public PQMsgPriority MsgPriority
    {
        get { return msgPriority; }
        set { msgPriority = value; }
    }
    public Object Message
    {
        get { return message; }
        set { message = value; }
    }
    #endregion

    public PQMessage(PQMsgPriority msgPriority, Object message)
    {
        this.msgPriority = msgPriority;
        this.message = message;
    }
}

優先キューを実装するための他のアプローチがある場合は、正しい方向に向けてください。

4

2 に答える 2

2

(防弾実装ではなく学習のためにこれを行っていると仮定して、これを免責する必要があります。うまく機能するものが必要な場合は、既存の実装を再利用することをお勧めします)。

ごく一般的なコメントです。以下の例では、3 行目は不要です。

Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
dataList.Enqueue(item);
messageDictionary[item.MsgPriority] = dataList;

dataListから返されるmessageDictionaryは、マップ内の参照のコピーです。これは、データを処理するときにEnqueue、以前と同じ基礎となるキュー (キューのコピーではない) で作業していることを意味します。したがって、再度元に戻す必要はなく、その行を削除するだけで済みます。

デキューの実装では、毎回最初の要素で中断するループがあります (たとえば、ループを 1 周するだけです)。おそらく、LINQ を使用してFirst要素を取得し、それをすぐに返すことを調査できますか? （同様にPeek実装`）。

最後に、PQMessageそれ自体が優先される場合、実装に を使用することを検討できSortedListますか? （こちらをご覧ください）

于 2012-05-16T06:37:33.850 に答える
1

同時実行のパフォーマンスを向上させる必要がある場合は、書き込み用に1つのキューのみをロックできます。（SortedDictionary全体の読み取りロックはまだニードされています）。

そして、正しい順序でロックを設定および解放することを忘れないでください

于 2012-05-16T06:51:15.153 に答える