Реализация очереди приоритетов в C#

Question

Я пытаюсь реализовать механизм очереди приоритетов с использованием 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; 
    } 
} 

Если есть любой другой подход для реализации очереди с приоритетами, пожалуйста, мне точку в правильном направлении.

Answer 1

(Я должен просто отказаться от этого, я предполагаю, что вы делаете это для обучения, а не для пуленепробиваемой реализации. Если хотите что-то, что только работает, то вам лучше повторить использование существующей реализации).

Несколько общих замечаний. В приведенном ниже примере третья строка не нужна.

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

dataList вы получите вернулись из messageDictionary копии ссылки в карте. Это означает, что когда вы делаете Enqueue данные, он работает в одной и той же базовой очереди, как раньше (а не в копии очереди), поэтому нет необходимости возвращать ее обратно, вы можете просто удалить эту строку.

В вашей реализации dequeue у вас есть цикл, в котором вы каждый раз ломаетесь по первому элементу (например, вы только когда-либо обходите цикл один раз). Возможно, вы можете исследовать с помощью LINQ, чтобы получить элемент First и сразу же вернуть его прямо сейчас? (аналогично для реализации Peek).

И, наконец, укажите, что PQMessage имеет приоритет, возможно, вы могли бы рассмотреть возможность использования SortedList для вашей реализации? (см. here)

Answer 2

Если вам необходимо улучшить совместимость, вы можете заблокировать только одну очередь для записи. (Чтение блокировки для всего SortedDictionary по-прежнему неидентифицировано).

И не забудьте установить и освободить замки в правильном порядке