Lookup()和Dictionary(列表()之间的区别)

Question

我试图围绕哪些数据结构最有效以及何时/何地使用哪些数据结构.

现在,可能是因为我只是不太了解这些结构,但是如何与一个ILookup(of key, ...)不同Dictionary(of key, list(of ...))？

另外,我想在ILookup哪里使用？在程序速度/内存/数据访问等方面哪个更高效？

Answer 1

两个显着差异:

• Lookup是不可改变的.是的:)(至少,我相信具体Lookup类是不可变的,并且ILookup接口不提供任何变异成员.当然可能还有其他可变实现.)
• 当您查找查找中不存在的键时,将返回空序列而不是a KeyNotFoundException.(因此没有TryGetValue,AFAICR.)

它们可能在效率上相当 - 例如,查找可能会Dictionary<TKey, GroupingImplementation<TValue>>在幕后使用.根据您的要求在它们之间进行选择.我个人认为查找通常比a更合适Dictionary<TKey, List<TValue>>,主要是由于上面的前两点.

请注意,作为一个实现细节,其具体实现IGrouping<,>用于值实现IList<TValue>,这意味着它的使用效率很高Count(),ElementAt()等等.

Answer 2

有趣的是,没有人说出实际的最大差异(直接来自MSDN):

查找类似于字典.区别在于Dictionary将键映射到单个值,而Lookup将键映射到值集合.

Answer 3

a Dictionary<Key, List<Value>>和Lookup<Key, Value>逻辑上都可以保存以类似方式组织的数据,并且两者具有相同的效率顺序.主要的区别是a Lookup是不可变的:它没有Add()方法,也没有公共构造函数(正如Jon所说,你可以在没有异常的情况下查询不存在的密钥,并将密钥作为分组的一部分).

至于你使用哪个,它实际上取决于你想如何使用它们.如果你要维护一个不断被修改的多个值的键的映射,那么a Dictionary<Key, List<Value>>可能更好,因为它是可变的.

但是,如果您有一系列数据并且只想要按键组织的数据的只读视图,那么查找很容易构建,并且会为您提供只读快照.

Answer 4

a ILookup<K,V>和a 之间的主要区别在于Dictionary<K, List<V>>字典是可变的; 您可以添加或删除密钥,还可以在查找的列表中添加或删除项目.An ILookup是不可变的,一旦创建就无法修改.

两种机制的底层实现将是相同或相似的,因此它们的搜索速度和内存占用量将大致相同.

Answer 5

尚未提及的另一个区别是Lookup()支持null键:

Lookup类实现ILookup接口.Lookup非常类似于字典,除了允许多个值映射到同一个键,并且支持null键.

Answer 6

当异常不是一个选项时，去查找

如果您试图获得与 a 一样有效的结构，Dictionary但您不确定输入中没有重复的键，Lookup则更安全。

正如另一个答案中提到的，它还支持空键，并且在使用任意数据查询时始终返回有效结果，因此它似乎对未知输入更具弹性（比字典更不容易引发异常）。

如果将其与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