Bộ sưu tập nhanh nhất trong C# để triển khai hàng đợi ưu tiên là gì?

Question

Tôi cần triển khai hàng đợi FIFO cho các thư trên máy chủ trò chơi để nó cần nhanh nhất có thể. Sẽ có một hàng đợi cho mỗi người dùng.

Hàng đợi sẽ có kích thước tối đa (cho phép nói 2000). Kích thước sẽ không thay đổi trong thời gian chạy.

Tôi cần ưu tiên thư CHỈ nếu hàng đợi đạt đến kích thước tối đa bằng cách làm việc ngược và xóa thông báo ưu tiên thấp hơn (nếu có) trước khi thêm thư mới.

Một ưu tiên là một int với giá trị có thể là 1, 3, 5, 7, 10

Có thể có nhiều tin nhắn với các ưu tiên như nhau.

Thông báo không thể thay đổi mức ưu tiên của nó khi được phân bổ.

Ứng dụng không đồng bộ để truy cập vào hàng đợi cần được khóa.

Tôi hiện đang triển khai nó bằng cách sử dụng LinkedList làm bộ nhớ cơ bản nhưng có lo ngại rằng việc tìm kiếm và xóa các nút sẽ giữ cho khóa bị khóa quá lâu.

Heres mã cơ bản tôi có vào lúc này:

public class ActionQueue 
{ 
    private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>(); 
    private int _maxSize; 

    /// <summary> 
    /// Initializes a new instance of the ActionQueue class. 
    /// </summary> 
    public ActionQueue(int maxSize) 
    { 
     _maxSize = maxSize; 
    } 

    public int Count 
    { 
     get { return _actions.Count; }    
    } 

    public void Enqueue(ClientAction action) 
    { 
     lock (_actions) 
     { 
      if (Count < _maxSize) 
       _actions.AddLast(action); 
      else 
      { 
       LinkedListNode<ClientAction> node = _actions.Last; 
       while (node != null) 
       { 
        if (node.Value.Priority < action.Priority) 
        { 
         _actions.Remove(node); 
         _actions.AddLast(action); 
         break; 
        } 

        node = node.Previous; 

       }      
      } 
     } 
    } 

    public ClientAction Dequeue() 
    { 
     ClientAction action = null; 

     lock (_actions) 
     { 
      action = _actions.First.Value; 
      _actions.RemoveFirst(); 
     } 

     return action; 
    } 

} 

Answer 1

Vì vậy, chúng tôi có các thuộc tính sau:

• ưu tiên được xác định rõ và bị chặn
• nhu cầu được thread-safe
kích thước
• Queue là cố định đến năm 2000 thông điệp , trong đó đồ uống vượt quá mức giảm này, mặt hàng thấp nhất

của nó rất dễ dàng để viết một hàng đợi ưu tiên, hỗ trợ tất cả các thuộc tính:

public class BoundedPriorityQueue<T> 
{ 
    private object locker; 
    private int maxSize; 
    private int count; 
    private LinkedList<T>[] Buckets; 

    public BoundedPriorityQueue(int buckets, int maxSize) 
    { 
     this.locker = new object(); 
     this.maxSize = maxSize; 
     this.count = 0; 
     this.Buckets = new LinkedList<T>[buckets]; 
     for (int i = 0; i < Buckets.Length; i++) 
     { 
      this.Buckets[i] = new LinkedList<T>(); 
     } 
    } 

    public bool TryUnsafeEnqueue(T item, int priority) 
    { 
     if (priority < 0 || priority >= Buckets.Length) 
      throw new IndexOutOfRangeException("priority"); 

     Buckets[priority].AddLast(item); 
     count++; 

     if (count > maxSize) 
     { 
      UnsafeDiscardLowestItem(); 
      Debug.Assert(count <= maxSize, "Collection Count should be less than or equal to MaxSize"); 
     } 

     return true; // always succeeds 
    } 

    public bool TryUnsafeDequeue(out T res) 
    { 
     LinkedList<T> bucket = Buckets.FirstOrDefault(x => x.Count > 0); 
     if (bucket != null) 
     { 
      res = bucket.First.Value; 
      bucket.RemoveFirst(); 
      count--; 
      return true; // found item, succeeds 
     } 
     res = default(T); 
     return false; // didn't find an item, fail 
    } 

    private void UnsafeDiscardLowestItem() 
    { 
     LinkedList<T> bucket = Buckets.Reverse().FirstOrDefault(x => x.Count > 0); 
     if (bucket != null) 
     { 
      bucket.RemoveLast(); 
      count--; 
     } 
    } 

    public bool TryEnqueue(T item, int priority) 
    { 
     lock (locker) 
     { 
      return TryUnsafeEnqueue(item, priority); 
     } 
    } 

    public bool TryDequeue(out T res) 
    { 
     lock (locker) 
     { 
      return TryUnsafeDequeue(out res); 
     } 
    } 

    public int Count 
    { 
     get { lock (locker) { return count; } } 
    } 

    public int MaxSize 
    { 
     get { return maxSize; } 
    } 

    public object SyncRoot 
    { 
     get { return locker; } 
    } 
} 

Hỗ trợ Enqueue/Dequeue trong thời gian O (1) thời gian, các phương pháp TryEnqueue và TryDequeue được đảm bảo để được thread-an toàn, và kích thước của bộ sưu tập sẽ không bao giờ vượt quá kích thước tối đa bạn chỉ định trong hàm tạo.

Khóa trên TryEnqueue và TryDequeue khá chi tiết, vì vậy bạn có thể thực hiện một lần truy cập hiệu suất bất cứ khi nào bạn cần tải hoặc tải dữ liệu hàng loạt. Nếu bạn cần tải hàng đợi với nhiều dữ liệu lên phía trước, hãy khóa trên SyncRoot và gọi các phương thức không an toàn nếu cần.

Answer 2

tôi giả sử bạn có thể có ưu tiên trùng lặp.

Không có vùng chứa trong .NET cho phép các khóa trùng lặp giống với đa thức C++. Bạn có thể làm điều này theo một vài cách khác nhau, hoặc với một SortedList có một mảng giá trị cho mỗi khóa ưu tiên (và lấy mục đầu tiên ra khỏi mảng đó làm giá trị trả về); SortedList là một cây cân bằng bên dưới (IIRC) và sẽ cho bạn hiệu suất chèn và truy xuất tốt.

Answer 3

Việc triển khai thực hiện hàng đợi ưu tiên cho C# /. NET có thể được tìm thấy trong số C5 Generic Collection Library trong lớp C5.IntervalHeap<T>.

Answer 4

Nếu bạn có số lượng ưu tiên cố định, tôi chỉ cần tạo một lớp Queue hỗn hợp bao bọc hai hoặc nhiều Hàng đợi riêng tư.

Ví dụ đơn giản hóa mạnh mẽ theo mặc dù bạn có thể mở rộng bằng cách thêm một mức độ ưu tiên enum và một công tắc để xác định nơi để Enqueue một mục.

class PriorityQueue { 

    private readonly Queue normalQueue = new Queue(); 
    private readonly Queue urgentQueue = new Queue(); 

    public object Dequeue() { 
     if (urgentQueue.Count > 0) { return urgentQueue.Dequeue(); } 
     if (normalQueue.Count > 0) { return normalQueue.Dequeue(); } 
     return null; 
    } 

    public void Enqueue(object item, bool urgent) { 
     if (urgent) { urgentQueue.Enqueue(item); } 
     else { normalQueue.Enqueue(item); } 
    } 
} 

Answer 5

Nó thực sự phụ thuộc vào phân phối độ dài hàng đợi mà bạn có khả năng thấy. 2000 là giá trị tối đa nhưng giá trị trung bình và phân phối trông như thế nào? Nếu N thường nhỏ, một Danh sách đơn giản <> với tìm kiếm bạo lực cho mức thấp nhất tiếp theo có thể là một lựa chọn tốt.

Bạn đã lược tả đơn đăng ký của mình là biết đây có phải là nút cổ chai không?

  "Never underestimate the power of a smart compiler 
      and a smart CPU with registers and on-chip memory 
      to run dumb algorithms really fast"