Наиболее эффективная реализация коллекций UniqueQueue и UniqueReplacementQueue в .NET

Question

Какова наиболее эффективная (с точки зрения скорости) реализация коллекций UniqueQueue и UniqueReplacementQueue в .NET, учитывая тот факт, что скорость операций Enqueue и Dequeue одинаково важна.

UniqueQueue - очередь, в которой дублируютсяне возможно.Поэтому, если я помещаю элемент в очередь, он добавляется только в том случае, если он еще не существует в очереди.

UniqueReplacementQueue - это очередь, в которой дублирование также невозможно.Разница в том, что если я нажимаю элемент, который уже существует в очереди, он заменяет существующий элемент в той же позиции.Это имеет смысл для ссылочных типов.

Моя текущая реализация UniqueQueue и UniqueReplacementQueue:

sealed class UniqueQueue<T> : IQueue<T>
{
    readonly LinkedList<T> list;
    readonly IDictionary<T, int> dictionary;

    public UniqueQueue(LinkedList<T> list, IDictionary<T, int> dictionary)
    {
        this.list = list;
        this.dictionary = dictionary;
    }

    public int Length
    {
        get { return list.Count; }
    }

    public T Dequeue()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        var element = list.First.Value;
        dictionary.Remove(element);
        list.RemoveFirst();

        return element;
    }

    public void Enqueue(T element)
    {
        dictionary[element] = 0;

        if (dictionary.Count > list.Count)
        {
            list.AddLast(element);
        }
    }
}

sealed class UniqueReplacementQueue<T> : IQueue<T>
{
    readonly LinkedList<T> list;
    readonly IDictionary<T, T> dictionary;

    public UniqueReplacementQueue(LinkedList<T> list, IDictionary<T, T> dictionary)
    {
        this.list = list;
        this.dictionary = dictionary;
    }

    public int Length
    {
        get { return list.Count; }
    }

    public T Dequeue()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        var element = dictionary[list.First.Value];
        dictionary.Remove(element);
        list.RemoveFirst();

        return element;
    }

    public void Enqueue(T element)
    {
        dictionary[element] = element;

        if (dictionary.Count > list.Count)
        {
            list.AddLast(element);
        }
    }
}

Answer 1

Это довольно старый, но как насчет класса, который имеет внутренний HashSet и Queue. Пользовательский метод Enqueue сначала пытается добавить его в хэш-набор. если вызов HashSet.Add возвращает false, мы не ставим его в очередь. HashSet.Add () является операцией O (1), если набор имеет размер, достаточно большой, чтобы вместить все элементы.

Единственный недостаток - использование памяти, если это вас беспокоит. Вот реализация:

public class UniqueQueue<T> : IEnumerable<T> {
    private HashSet<T> hashSet;
    private Queue<T> queue;


    public UniqueQueue() {
        hashSet = new HashSet<T>();
        queue = new Queue<T>();
    }


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

    public void Clear() {
        hashSet.Clear();
        queue.Clear();
    }


    public bool Contains(T item) {
        return hashSet.Contains(item);
    }


    public void Enqueue(T item) {
        if (hashSet.Add(item)) {
            queue.Enqueue(item);
        }
    }

    public T Dequeue() {
        T item = queue.Dequeue();
        hashSet.Remove(item);
        return item;
    }


    public T Peek() {
        return queue.Peek();
    }


    public IEnumerator<T> GetEnumerator() {
        return queue.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        return queue.GetEnumerator();
    }
}

HashSet используется всегда, когда это возможно, потому что обычно он быстрее. Это могло бы быть лучше, если бы сопровождающие .NET отметили эти методы как виртуальные, но, увы, мы здесь.

Answer 2

Как насчет этого?

//the UniqueQueueItem has the key in itself,
//and implements the IUniqueQueueItemable to copy the other values.
//For example:
class TestUniqueQueueItem : IUniqueQueueItemable<TestUniqueQueueItem>
{
    //Key
    public int Id { get; set; }
    public string Name { get; set; }
    public override int GetHashCode()
    {
        return Id;
    }

    //To copy the other values.
    public void CopyWith(TestUniqueQueueItem item)
    {
        this.Name = item.Name;
    }

    public override bool Equals(object obj)
    {
        return this.Id == ((TestUniqueQueueItem)obj).Id;
    }
}

internal interface IUniqueQueueItemable<in T>
{
    void CopyWith(T item);
}

class UniqueQueue<T> where T: IUniqueQueueItemable<T>
{
    private readonly bool _isReplacementQueue;
    private readonly Queue<T> _queue;
    private readonly Dictionary<T, T> _dictionary;

    public UniqueQueue(): this(false)
    {
    }

    public UniqueQueue(bool isReplacementQueue)
    {
        _isReplacementQueue = isReplacementQueue;
        _queue = new Queue<T>();
        _dictionary = new Dictionary<T, T>();
    }

    public void Enqueue(T item)
    {
        if(!_dictionary.Keys.Contains(item))
        {
            _dictionary.Add(item, item);
           _queue.Enqueue(item);
        }
        else
        {
            if(_isReplacementQueue)
            {
                //it will return the existedItem, which is the same key with the item 
                //but has different values with it.
                var existedItem = _dictionary[item];

                //copy the item to the existedItem. 
                existedItem.CopyWith(item);
            }
        }
    }

    public T Dequeue()
    {
        var item = _queue.Dequeue();
        _dictionary.Remove(item);
        return item;
    }
}