我有一个关于C#中泛型集合的问题。如果我需要存储项目集合,而且我经常需要检查项目是否在集合中,那么使用Dictionary而不是List会更快吗?使用字典<Foo, Foo>而不是列表<Foo>加速调用包含()
我听说检查一个项目是否在集合中是线性相对于列表的大小和常量相对于字典的大小。是使用Dictionary,然后将Key和Value设置为每个键值对的同一对象,这是其他程序员在这种情况下经常做的事情?
感谢您花时间阅读本文。
我有一个关于C#中泛型集合的问题。如果我需要存储项目集合,而且我经常需要检查项目是否在集合中,那么使用Dictionary而不是List会更快吗?使用字典<Foo, Foo>而不是列表<Foo>加速调用包含()
我听说检查一个项目是否在集合中是线性相对于列表的大小和常量相对于字典的大小。是使用Dictionary,然后将Key和Value设置为每个键值对的同一对象,这是其他程序员在这种情况下经常做的事情?
感谢您花时间阅读本文。
是的,是的。也就是说,你可能想要使用HashSet
,因为你不需要一个键和一个值,你只需要一组物品。
另外值得一提的是,Dictionary
添加在C#2.0,并在3.5加入HashSet
,所以所有的时间插图中它实际上是相当普遍的,当你想要一个设置为使用字典,只是因为这是所有你有(没有滚动你自己)。当我被迫做这件事时,我只是在价值中坚持了空值,而不是作为关键和价值的项目,但这个想法是相同的。
谢谢你们!这正是我需要知道的。我非常肯定,使用字典
只要使用HashSet<Foo>
如果你关心的是快速遏制测试。
A Dictionary<TKey, TValue>
用于查找基于密钥的值。
A List<T>
用于随机存取和动态增长特性。
A HashSet<T>
用于模拟一套和提供快速的遏制测试。
您没有查找基于密钥的值。您不担心随机访问,而是快速收容检查。这里的正确概念是HashSet<T>
。
Dictionary或HashSet将使用更多内存,但提供(几乎)O(1)查找时间。
假设列表中只有该项目的一个副本,则适当的数据结构为ISet<T>
,特别是HashSet<T>
。
也就是说,我看过的时间表明Dictionary<TKey, TValue>
ContainsKey
呼叫比HashSet<T>
要快。无论哪种方式,它们都将比普通的查找加载速度更快。
请记住,这两种方法(HashSet的词典)依靠合理地实现Equals
和GetHashcode
实现了T
。 List<T>
只依赖于Equals
您可能想看看HashSet,它是唯一对象的集合(只要该对象实现了IEquality比较器)。
您提到使用List<T>
,这意味着排序可能很重要。如果是这种情况,那么你可能也想看看SortedSet<T>
类型。
列表中有多少项?如果你有100个,这将是预先优化,并没有关系。 –
您正在使用'Dioctionary',就像'HashSet '一样,技术上应该更快,但您应该使用'Stopwatch'来比较它们。 –
BeemerGuy
重复。请参阅http://stackoverflow.com/questions/1009107/what-net-collection-provides-the-fastest-search。 – JamieSee