我正在努力思考哪些数据结构是最有效的,以及何时/何处使用哪些数据结构。
现在,这可能是我只是不理解结构不够好,但如何是一个ILookup(键,…)不同于字典(键,列表(…))?
另外,我想在哪里使用ILookup,在哪里它在程序速度/内存/数据访问等方面更有效?
我正在努力思考哪些数据结构是最有效的,以及何时/何处使用哪些数据结构。
现在,这可能是我只是不理解结构不够好,但如何是一个ILookup(键,…)不同于字典(键,列表(…))?
另外,我想在哪里使用ILookup,在哪里它在程序速度/内存/数据访问等方面更有效?
当前回答
两个显著的区别:
查找是不可变的。(至少,我相信具体的Lookup类是不可变的,并且ILookup接口不提供任何变化的成员。当然,还可以有其他可变的实现。) 当您查找查找中不存在的键时,将返回一个空序列,而不是KeyNotFoundException。(因此没有TryGetValue, AFAICR。)
它们在效率上可能是等效的——例如,在幕后查找很可能使用Dictionary<TKey, GroupingImplementation<TValue>>。根据您的需求在它们之间进行选择。就我个人而言,我发现查找通常比Dictionary<TKey, List<TValue>>更适合,主要是因为上面的前两点。
请注意,作为实现细节,用于值的IGrouping<,>的具体实现实现了IList<TValue>,这意味着它与Count(), ElementAt()等一起使用是有效的。
其他回答
两个显著的区别:
查找是不可变的。(至少,我相信具体的Lookup类是不可变的,并且ILookup接口不提供任何变化的成员。当然,还可以有其他可变的实现。) 当您查找查找中不存在的键时,将返回一个空序列,而不是KeyNotFoundException。(因此没有TryGetValue, AFAICR。)
它们在效率上可能是等效的——例如,在幕后查找很可能使用Dictionary<TKey, GroupingImplementation<TValue>>。根据您的需求在它们之间进行选择。就我个人而言,我发现查找通常比Dictionary<TKey, List<TValue>>更适合,主要是因为上面的前两点。
请注意,作为实现细节,用于值的IGrouping<,>的具体实现实现了IList<TValue>,这意味着它与Count(), ElementAt()等一起使用是有效的。
如果没有exception选项,则选择Lookup
如果你试图获得一个像Dictionary一样高效的结构,但你不确定输入中是否有重复的键,Lookup更安全。
正如在另一个答案中提到的,它还支持空键,并且在使用任意数据查询时总是返回有效结果,因此它似乎对未知输入更有弹性(比Dictionary更不容易引发异常)。
如果你将它与System.Linq.Enumerable.ToDictionary函数进行比较,尤其如此:
// won't throw
new[] { 1, 1 }.ToLookup(x => x);
// System.ArgumentException: An item with the same key has already been added.
new[] { 1, 1 }.ToDictionary(x => x);
另一种方法是在foreach循环中编写自己的重复密钥管理代码。
性能方面的考虑,Dictionary:一个明显的赢家
如果你不需要一个列表,你要管理大量的项目,字典(甚至是你自己定制的结构)会更有效:
Stopwatch stopwatch = new Stopwatch();
var list = new List<string>();
for (int i = 0; i < 5000000; ++i)
{
list.Add(i.ToString());
}
stopwatch.Start();
var lookup = list.ToLookup(x => x);
stopwatch.Stop();
Console.WriteLine("Creation: " + stopwatch.Elapsed);
// ... Same but for ToDictionary
var lookup = list.ToDictionary(x => x);
// ...
由于Lookup必须为每个键维护一个项列表,因此它比Dictionary慢(对于大量项,大约慢3倍)
查找速度: 创造:00:00:01.5760444 字典的速度: 创造:00:00:00.4418833
有趣的是,没有人说出实际最大的区别(直接来自MSDN):
查找类似于字典。的 不同之处在于Dictionary将键映射为single 的集合,而Lookup则将键映射到 值。
Dictionary<Key, List<Value>>和Lookup<Key, Value>在逻辑上都可以保存以类似方式组织的数据,并且两者的效率顺序相同。主要的区别是Lookup是不可变的:它没有Add()方法,也没有公共构造函数(正如Jon提到的,您可以查询一个不存在的键而没有异常,并将键作为分组的一部分)。
至于你用哪一种,实际上取决于你想如何使用它们。如果您正在维护一个键到多个值的映射,这些值经常被修改,那么Dictionary< key, List<Value>>可能更好,因为它是可变的。
但是,如果您有一个数据序列,并且只想要一个按键组织的数据的只读视图,那么查找非常容易构造,并将给您一个只读快照。
ILookup<K,V>和Dictionary<K, List<V>>之间的主要区别是字典是可变的;您可以添加或删除键,也可以从所查找的列表中添加或删除项。ILookup是不可变的,一旦创建就不能修改。
这两种机制的底层实现将是相同或相似的,因此它们的搜索速度和内存占用将大致相同。