c#中实现优先级排队队列的最快集合是什么？

Question

我需要为游戏服务器上的消息实现FIFO队列,因此它需要尽可能快.每个用户都会有一个队列.

队列将具有maxiumem大小(比方说2000).在运行时,大小不会改变.

我需要优先处理消息,如果队列通过向后工作并在添加新消息之前删除较低优先级的消息(如果存在),则达到其最大大小.

优先级是int,可能的值为1,3,5,7,10.

可以有多条具有相同优先级的消息.

一旦分配,消息就不能改变其优先级.

应用程序是异步的,因此需要锁定对队列的访问.

我目前正在使用LinkedList作为底层存储来实现它,但是担心搜索和删除节点会使其锁定时间过长.

这是我目前的基本代码:

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

可以在类中的C5通用集合库中找到C#/ .NET的优先级队列的审查实现C5.IntervalHeap<T>.

Answer 2

所以我们有以下属性：

• 优先事项是明确定义和有限的
• 需要线程安全
• 队列大小固定为 2000 条消息，超出此长度的队列会丢弃最低的项目

编写支持所有这些属性的优先级队列非常容易：

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

支持 O(1) 时间内的入队/出队，TryEnqueue 和 TryDequeue 方法保证线程安全，并且集合的大小永远不会超过您在构造函数中指定的最大大小。

TryEnqueue 和 TryDequeue 上的锁非常细粒度，因此每当需要批量加载或卸载数据时，性能可能会受到影响。如果您需要预先向队列加载大量数据，请锁定SyncRoot并根据需要调用不安全的方法。