Was ist die schnellste Sammlung in c#, um eine priorisierende Warteschlange zu implementieren?

Question

Ich brauche, um eine FIFO-Warteschlange für Nachrichten auf einem Spiel-Server zu implementieren, so dass es so schnell wie möglich muss. Es wird eine Warteschlange für jeden Benutzer sein.

Die Warteschlange wird eine maximale Größe haben (sagen wir 2000). Die Größe wird sich während der Laufzeit nicht ändern.

Ich muss Nachrichten NUR dann priorisieren, wenn die Warteschlange ihre maximale Größe erreicht, indem ich rückwärts arbeite und eine Nachricht mit niedrigerer Priorität (falls vorhanden) entferne, bevor ich die neue Nachricht hinzufüge.

Eine Priorität ist ein int mit möglichen Werten von 1, 3, 5, 7, 10.

Es kann mehrere Nachrichten mit der gleichen Priorität geben.

Eine einmal zugewiesene Nachricht kann ihre Priorität nicht mehr ändern.

Da die Anwendung asynchron arbeitet, muss der Zugriff auf die Warteschlange gesperrt werden.

Ich bin derzeit implementieren es mit einem LinkedList als die zugrunde liegende Speicherung, aber haben Bedenken, dass das Suchen und Entfernen von Knoten wird es zu lange gesperrt halten.

Hier ist der grundlegende Code, den ich im Moment habe:

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

Eine geprüfte Implementierung der Prioritätswarteschlange für C#/.NET finden Sie in der C5 Allgemeine Sammlungsbibliothek im C5.IntervalHeap<T> Klasse.

Answer 2

Wir haben also die folgenden Eigenschaften:

• Die Prioritäten sind klar definiert und eingegrenzt
• Muss thread-sicher sein
• Die Größe der Warteschlange ist auf 2000 Nachrichten festgelegt, wobei bei Warteschlangen, die diesen Wert überschreiten, das niedrigste Element fallen gelassen wird.

Es ist sehr einfach, eine Prioritätswarteschlange zu schreiben, die alle diese Eigenschaften unterstützt:

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

Unterstützt Enqueue/Dequeue in O(1)-Zeit, die TryEnqueue- und TryDequeue-Methoden sind garantiert thread-sicher, und die Größe der Sammlung wird nie die im Konstruktor angegebene Maximalgröße überschreiten.

Die Sperren von TryEnqueue und TryDequeue sind ziemlich feinkörnig, so dass es zu Leistungseinbußen kommen kann, wenn Sie Daten in großen Mengen laden oder entladen müssen. Wenn Sie die Warteschlange mit einer Menge von Daten im Voraus laden müssen, dann sperren Sie die SyncRoot und rufen die unsicheren Methoden nach Bedarf auf.

Answer 3

Wenn Sie eine feste Anzahl von Prioritäten haben, würde ich einfach eine zusammengesetzte Queue-Klasse erstellen, die zwei oder mehr private Queues umschließt.

Es folgt ein drastisch vereinfachtes Beispiel, das man allerdings noch erweitern könnte, indem man ein Prioritäts-Enum und einen Schalter hinzufügt, um zu bestimmen, wo ein Element eingereiht werden soll.

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 4

Ich gehe davon aus, dass Sie doppelte Prioritäten haben können.

Es gibt keinen Container in .NET, der doppelte Schlüssel ähnlich wie eine C++-Multimap erlaubt. Sie könnten dies in ein paar verschiedene Möglichkeiten zu tun, entweder mit einem SortedList, die ein Array von Werten für jede Priorität Schlüssel hatte (und greifen das erste Element aus diesem Array als Rückgabewert); die SortedList ist ein ausgeglichener Baum unter (IIRC) und sollten Sie gute Einfügen und Abrufen Leistung geben.

Answer 5

Es hängt wirklich von der Verteilung der Warteschlangenlängen ab, die Sie wahrscheinlich sehen werden. 2000 ist das Maximum, aber wie sieht der Durchschnitt aus und wie sieht die Verteilung aus? Wenn N typischerweise klein ist, kann eine einfache Liste<> mit einer Brute-Force-Suche nach dem nächstkleineren Wert eine gute Wahl sein.

Haben Sie ein Profil Ihrer Anwendung erstellt, um wissen dies ein Engpass ist?

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