C#中速度最快,效率最高的集合类型

Question

我正在构建一个应用程序,需要一个集合来容纳大约10k的字符串.

集合将用作队列.

因此,在C#中查看不同的集合类型,但无法确定哪一个在Queue中执行Put和Get操作的速度方面具有最佳性能.也应该能够不允许在队列/集合中重复.

根据评论编辑..

任何现有的收藏都会有所帮助.或者可以执行任何现有集合的自定义集合将是很棒的.

谢谢

Answer 1

如果您正在寻找高性能Put&Get,同时检查唯一性(重复检查)但订单无关紧要(不是队列)然后使用HashSet<T>

如果队列功能更重要,那么使用a Queue<T>

我不认为有什么可以提供.

Answer 2

你介意花O(2n)记忆吗？您可以将Queue <>与Dictionary <,>结合使用.队列将处理队列和出列操作,字典将确保唯一条目.一个简单的包装器类可以组合这两个,它会给你O(log n)队列和出队时间.

例:

public class SetQueue<T>
{
    private readonly Dictionary<T, bool> duplicates = new Dictionary<T, bool>();
    private readonly Queue<T> queue = new Queue<T>();

    public bool Enqueue(T item)
    {
        if (!duplicates.ContainsKey(item))
        {
            duplicates[item] = true;

            queue.Enqueue(item);

            return true;
        }

        return false;
    }

    public T Dequeue()
    {
        if (queue.Count >0)
        {
            var item = queue.Dequeue();
            if (!duplicates.ContainsKey(item))
                throw new InvalidOperationException("The dictionary should have contained an item");
            else
                duplicates.Remove(item);

            return item;
        }

        throw new InvalidOperationException("Can't dequeue on an empty queue.");
    }
}

插入此自定义数据结构中检查字典是否已包含该项目.此操作使用ContainsKey方法,该方法是O(log n)操作.如果该项已包含在数据结构中,则该方法已退出.如果未包含该项,则该项将被插入到队列中,该队列是常量O(1)操作.它也将被添加到字典中.当字典的计数小于容量时,这将接近常数,O(1)插入时间.因此总队列时间为O(log n).

出列方法也是如此.

此解决方案与内置数据结构OrderedDictionary基本相同,但是,由于此解决方案使用通用,因此在装箱操作中没有任何开销,从而使其浪费更快.

Answer 3

还有就是OrderedDictionary这使插入顺序,但允许您通过键查找值类.