问题描述

考虑到 Enqueue 和 Dequeue 操作的速度同样重要这一事实，.NET 中 UniqueQueue 和 UniqueReplacementQueue 集合的最有效(就速度而言)实现是什么.

What is the most efficient (in terms of speed) implementation of UniqueQueue and UniqueReplacementQueue collections in .NET considering the fact that the speed of Enqueue and Dequeue operations is equally important.

UniqueQueue 是一个不可能重复的队列.因此，如果我将一个元素推送到队列中，它只会在队列中不存在的情况下添加.

UniqueQueue is a queue where duplicates are not possible. So if I push an element to the queue it is added in only case it doesn't already exist in the queue.

UniqueReplacementQueue 是一个也不可能出现重复的队列.不同之处在于，如果我推送队列中已经存在的元素，它将替换相同位置的现有元素.这对引用类型很有意义.

UniqueReplacementQueue is a queue where duplicates are not possible either. The difference is that if I push an element which already exists in the queue, it replaces the existing element at the same position. It makes sense for reference types.

我目前对 UniqueQueue 和 UniqueReplacementQueue 的实现:

My current implementation of UniqueQueue and 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);
        }
    }
}

推荐答案

这已经很老了，但是有一个内部 HashSet 和 Queue 的类怎么样.Enqueue firsts 的自定义方法尝试将其添加到哈希集中.如果 HashSet.Add 调用返回 false，我们不会将其加入队列.如果集合的大小足以容纳所有元素，则 HashSet.Add() 是 O(1) 操作.

This is pretty old, but how about a class that has an internal HashSet, and Queue. A custom method for Enqueue firsts tries to add it to the hashset. if the HashSet.Add call returns false, we do not enqueue it. HashSet.Add() is an O(1) operation if the set is of a size large enough to hold all elements.

如果您担心，唯一的缺点是内存使用.这是一个实现:

The only drawback to this is memory usage if this is a concern for you. Here is an implementation:

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 的维护者将这些方法标记为虚拟方法，这可能会更好，但可惜我们到了.

The HashSet is used whenever it can because it is typically faster. This could be nicer if the maintainers of .NET marked these methods as virtual, but alas here we are.

这篇关于.NET 中 UniqueQueue 和 UniqueReplacementQueue 集合的最有效实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！