logo标签列表

Lookup()和Dictionary(Of list())的区别

c#.netvb.netlinq
224

我试图理解哪些数据结构是最有效的，以及何时/在哪里使用它们。

现在，可能只是因为我对这些结构不够了解，但是 ILookup (of key, ...) 与 Dictionary(of key, list(of ...)) 有什么区别？

此外，在程序速度/内存/数据访问效率方面，我应该在哪里使用 ILookup 以及何时使用更加高效？

1
有时候人们也想看一下what-is-the-point-of-lookuptkey-telement。 - nawfal
6个回答
331

两个显著的不同点：

  • Lookup是不可变的。太好了 :)（至少我认为具体的Lookup类是不可变的，并且ILookup接口没有提供任何变异成员。当然，可能会有其他可变实现。）
  • 当您查找一个不存在于查找中的键时，您会得到一个空序列而不是KeyNotFoundException。（因此，据我所知，没有TryGetValue。）

它们在效率上很可能是等效的 - 查找可能会在幕后使用Dictionary<TKey，GroupingImplementation<TValue>>，例如。根据您的要求选择它们之间的区别。就个人而言，由于上面的前两个原因，我通常发现查找通常比Dictionary<TKey，List<TValue>>更合适。

请注意，作为实现细节，用于值的IGrouping<，>的具体实现实现IList<TValue>，这意味着使用Count()，ElementAt()等非常高效。

3
如果一个不存在的键查找返回一个空序列而不是异常，那么在我看来它就不能作为通用集合。对于由linq查询产生的不可变集合而言，这种情况还可以接受。 - nawfal
@nawfal - 这正是查找表的用途。来自msdn："您可以通过在实现IEnumerable<T>的对象上调用ToLookup来创建Lookup<TKey，TElement>的实例。" - Niall Connaughton
1
@GoldenLion：这当然是“查找是不可变的”所覆盖的。 - Jon Skeet
假设您有十亿行数据，Lookup是否可行，因为它是可查询的，而字典会因内存限制而失败？ - Golden Lion
@GoldenLion：请不要试图使用评论线程来提出额外的问题。如果您想知道，请发布一个新问题（并付出研究和努力使其非常清晰和具体的努力）。 - Jon Skeet
显示剩余2条评论
108

有趣的是，没有人提到实际上最大的区别（直接从MSDN摘录）：

查找（Lookup）类似于字典（Dictionary）。不同之处在于字典将键映射到单个值，而查找将键映射到值的集合。

69
请检查问题：它的内容涉及Lookup<TKey, TValue>和Dictionary<TKey, List<TValue>>之间的区别，因此这种差异已经比较明显了。 - Martao
28
有些人在谷歌搜索时发现这个问题，想了解查找和字典之间的区别。这个答案非常有用。 - jakubiszon
@Mladen Mihajlovic，我不理解那个MSDN的解释。字典也可以将键映射到值的集合，例如通过传递一个列表：grouping.ToDictionary(g => g.Key, g => g.ToList())。 - OfirD
@OfirD 是的，在那个意义上它们是相同的。但正如其他答案所述，还有其他的区别。 - Mladen Mihajlovic
40

一个 Dictionary<Key, List<Value>> 和一个 Lookup<Key, Value> 都可以逻辑上以类似的方式组织数据，并且两者的效率相同。主要区别在于 Lookup 是不可变的：它没有 Add() 方法和公共构造函数（正如Jon所提到的，您可以查询不存在的键而不会抛出异常，并将键作为分组的一部分）。

关于使用哪种方法，这取决于您希望如何使用它们。如果您正在维护一个不断修改的键对多个值的映射，那么 Dictionary<Key, List<Value>> 可能更好，因为它是可变的。

然而，如果您有一系列数据并且只想通过键来组织数据的只读视图，则很容易构建一个 lookup 并为您提供只读快照。

15

还有一个尚未提到的区别是，Lookup() 支持空键：

Lookup类实现了ILookup接口。Lookup与字典非常相似，但允许多个值映射到同一个键，并支持空键。

14
ILookup<K,V> 和 Dictionary<K, List<V>> 的主要区别在于字典是可变的，您可以添加或删除键，并且还可以添加或删除查找列表中的项。而 ILookup 是不可变的，创建后不能修改。
两种机制的基本实现方式将是相同或类似的，因此它们的搜索速度和内存占用量大致相同。
1
在性能方面，不是的。这完全是逻辑上的。你可以传递结构引用而不必担心其他人会在你下面对其进行修改。你可以基于它是不可变的做出一些假设，如果它是可变的，你就无法做到这一点。 - Servy
谢谢，Servy，你说得很好。当你经常传递许多变量时，使用ByRef至少可以确保这个变量不会被修改。谢谢！ - John Bustos
2
@JohnBustos 请记住，传递方法参数的默认方法是按值传递，您需要显式添加byref，这应该很少做。这些数据结构是类，这使它们成为引用类型，因此传递值是引用的值，这就是为什么将其传递给另一个方法可能会导致调用者看到可见的更改。 - Servy
@Blam 我相当确定它确实有，但很可能不是完全相同的算法，只是类似的一般算法。 - Servy
关于@Servy评论中“默认参数传递方法是按值传递”的澄清......在C#中，默认情况下所有变量都是按值传递的。对于值类型，您正在进行复制。而对于引用类型，您正在传递引用的值（而不是复制）。当然，除非您添加了ref关键字，它会传递ValueType的引用或ReferenceType的引用的引用。 - Dave Black
显示剩余2条评论
8

当异常不是可选项时，请选择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

4
我认为这个性能比较不公平。对于相同的结果，list.ToLookup(x => x) 和 list.GroupBy(x => x).ToDictionary(group => group.Key) 是相等的。因为像你一开始所说的那样，Lookup可以枚举重复的元素。 - PM Extra
为了提高性能，更有趣的是从ILookup或Dictionary中检索。典型的用法是仅创建一次，并进行频繁的查找。因此，我不太关心构建它的性能。 - GreatBittern
感谢您的撰写。我想指出，“性能考虑”部分可能需要更多的明确性，因为它不舒服地暗示了当Lookup执行其未设计的操作时，即将1个键映射到1个值时，其性能会变差。 - Mr.Z
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接