C#中最快、最高效的集合类型是什么？

Question

我正在构建一个应用程序，需要使用一个集合来存储大约10k个字符串。

这个集合将被用作队列。

因此，我查看了 C# 中不同的集合类型，但无法确定哪种集合在排队时以速度最快地执行 Put 和 Get 操作方面具有最佳性能。同时还要能够防止队列/集合中出现重复项。

根据评论编辑:

任何现有的集合都会有所帮助。或者一个可以比任何现有集合表现更好的自定义集合将是很好的选择。

谢谢

- Kamil Dhuleshia

---

使用数组作为FIFO队列怎么样？ - eat_a_lemon

考虑使用ArrayList，但是在搜索方面表现非常糟糕，而Dictionary在执行搜索时非常出色，但需要更多的资源和时间来进行put和get操作... - Kamil Dhuleshia

如果有一种最快的集合，那么其他所有集合都将变得无用 :) 请告诉我们您需要一个快速插入新项的集合还是一个快速读取的集合（如果您只构建它一次并且只从中读取，这将产生巨大的差异）。此外，内存使用是否成问题？字符串有多长？ - Michael Stum

这是一个毫无意义的问题。它表明 Queue<> 有问题，但从未说明具体在哪里。如果有更好的队列实现方式，当然 .NET 框架的程序员们会采用它。你做不到更好，只能做得更糟。 - Hans Passant

Answer 1

如果您正在寻找高性能的Put & Get，同时检查唯一性（重复检查），但顺序不重要（不是队列），则使用HashSet<T>

如果队列功能更重要，则使用Queue<T>

我认为没有任何东西可以同时提供两者。

- Sanjeevakumar Hiremath

---

他正在寻找一个快速的解决方案，以实现具有唯一条目的队列系统。您为其中一个条件提供了解决方案，但不能同时满足两个条件。 - Kasper Holdum

我说过，任何一个数据结构都不可能立即实现这一点。不是这样吗？ - Sanjeevakumar Hiremath

从问题陈述的方式来看，这是一个正确的答案。问题似乎在寻找一个现有的集合类型，但它并没有解决原始问题背后的意图，但我们无法读取他的想法。 - Joel Lee

请注意编辑：“任何能够胜过现有解决方案的自定义数据类型”。我发布的解决方案可以满足所有要求，同时提供出色的性能。 - Kasper Holdum

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相同，但由于这个解决方案使用了泛型，所以在其操作中没有装箱/拆箱的开销，使其更快。

- Kasper Holdum

---

这是一个可能的解决方案...或者我可以使用包含所有集合数据的字典，并使用队列作为缓冲区从字典中获取子集数据。任何评论？ - Kamil Dhuleshia

我不确定你所说的使用队列作为缓冲区从字典中获取子集数据的意思是什么？ - Kasper Holdum

遍历存储在字典中的所有数据是一项缓慢的操作。你为什么不像我在示例代码中那样始终保持两者同步呢？我认为你需要更具体地说明你真正想要做什么。条目应该是唯一的，还是相同的条目应该被分组？ - Kasper Holdum

是的，它很高效。高效意味着提供最小浪费努力的解决方案。尝试想出一种使用更少空间同时提供更好性能的解决方案。 - Kasper Holdum

我的解决方案的性能比被接受的答案高出一个数量级，而且它们都使用相同的内存量。 - Kasper Holdum

Answer 3

有一个 OrderedDictionary 类，它保留插入顺序，但允许您通过键查找值。

- ChrisWue