Jaka jest najszybsza kolekcja w języku C# do wdrożenia kolejki priorytetyzacji?

Question

Potrzebuję zaimplementować kolejkę FIFO dla wiadomości na serwerze gry, więc musi być tak szybko jak to możliwe. Dla każdego użytkownika będzie kolejka.

Kolejka będzie miała maksymalny rozmiar (powiedzmy 2000). Rozmiar nie zmieni się podczas uruchamiania.

Muszę TYLKO nadać priorytet wiadomościom, jeśli kolejka osiągnie maksymalny rozmiar, pracując wstecz i usuwając komunikat o niższym priorytecie (jeśli taki istnieje) przed dodaniem nowej wiadomości.

priorytet jest int z możliwych wartości o 1, 3, 5, 7, 10.

może istnieć wiele wiadomości z tym samym priorytecie.

Po przydzieleniu wiadomość nie może zmienić swojego priorytetu.

Aplikacja jest asynchroniczna, dlatego dostęp do kolejki musi być zablokowany.

W tej chwili implementuję go przy użyciu obiektu LinkedList jako bazowego magazynu, ale mam obawy, że wyszukiwanie i usuwanie węzłów pozostanie zablokowane przez zbyt długi czas.

Herezje kod podstawowy Mam w tej chwili:

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

więc mamy następujące właściwości:

• Priorytety są dobrze zdefiniowane i ograniczone
• musi być bezpieczny wątku
rozmiar
• kolejka jest przymocowana do wiadomości 2000 , w przypadku gdy skrypty wykraczają poza ten spadek, najniższa pozycja:

Jego bardzo łatwo pisać kolejkę priorytetową, która obsługuje wszystkie z tych właściwości:

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; } 
    } 
} 

Podpory enqueue/rozkolejkowania w czasie O (1) czas, metody TryEnqueue i TryDequeue są gwarancją thread-safe, a rozmiar kolekcji nigdy nie przekroczy maksymalnego rozmiaru określonego w konstruktorze.

Zamki w TryEnqueue i TryDequeue są dość drobnoziarniste, więc możesz odnieść wrażenie wydajności, gdy potrzebujesz zbiorczego ładowania lub rozładowania danych. Jeśli musisz załadować kolejkę z dużą ilością danych z góry, zablokuj SyncRoot i w razie potrzeby wywołaj niebezpieczne metody.

Answer 2

Ja zakładając, że można mieć zduplikowanych priorytetów.

W systemie .NET nie ma kontenera, który umożliwia duplikowanie kluczy podobnych do wielościeżkowych C++. Można to zrobić na kilka różnych sposobów, korzystając z listy SortedList, która ma tablicę wartości dla każdego klucza priorytetu (i pobiera pierwszą pozycję z tej tablicy jako wartość zwracaną); the SortedList jest zrównoważonym drzewem pod spodem (IIRC) i powinien dać ci dobrą wydajność wstawiania i pobierania.

Answer 3

Sprawdzoną implementację kolejki priorytetowej dla języka C#/.NET można znaleźć w klasie C5 Generic Collection Library w klasie C5.IntervalHeap<T>.

Answer 4

Jeśli masz ustaloną liczbę priorytetów, po prostu utworzę złożoną klasę Queue, która otoczy dwie lub więcej prywatnych Queues.

Drastycznie uproszczony przykład jest kontynuowany, chociaż można go rozszerzyć, dodając wyodrębnienie priorytetu i przełącznik w celu określenia miejsca, w którym należy umieścić kolejkę.

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

To naprawdę zależy od rozkładu długości kolejek, które prawdopodobnie zobaczysz. 2000 to maksimum, ale jaka jest średnia i jak wygląda dystrybucja? Jeśli N jest zwykle mały, prosty wybór w przypadku szukania następnego najgorszego może być dobrym wyborem.

Czy profilowałeś swoje zgłoszenie do wiesz, to wąskie gardło?

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