时间戳

首页 > 解决方案 > LINQ ToDictionary 方法和复制字典迭代循环之间的性能差异

c# - LINQ ToDictionary 方法和复制字典迭代循环之间的性能差异

问题描述

在尝试查看ToDictionary使用迭代循环复制字典和使用迭代循环复制字典之间的差异时，我看到了非常大的性能差异。
在下面的代码中，我Dictionary<int, int>使用 LINQ 和非 LINQ 方式创建并复制了它。

编码：

public static void Main()
{
    const int originalDictionarySize = 10000;

    //////Creating Dictionary////////////// 
    var originalDictionary = new Dictionary<int, int>();
    for (var i = 0; i < originalDictionarySize; i++)
    {
        originalDictionary.Add(i, i);
    }
    //////Copy with Iterative Loop////////////// 
    IteraqtiveLoop(originalDictionary);

    //////Copy with LINQ///////////////////////// 
    CopyWIthLinq(originalDictionary);

    Console.ReadLine();
}

private static void IteraqtiveLoop(Dictionary<int, int> 
     originalDictionary)
{
    var sw = Stopwatch.StartNew();
    var dictionary2 = new Dictionary<int, int>(originalDictionary.Count);
    foreach (var kvp in originalDictionary)
    {
        dictionary2.Add(kvp.Key, kvp.Value);
    }
    sw.Stop();
    var endTime = sw.Elapsed;
    Console.WriteLine("The running time of copy with iterative loop: " + 
endTime);
}

private static void CopyWIthLinq(Dictionary<int, int> originalDictionary)
{
    var sw = Stopwatch.StartNew();
    var dictionary3 = originalDictionary.ToDictionary(i => i, i => i);
    sw.Stop();
    var endTime2 = sw.Elapsed;
    Console.WriteLine("The running time of copy with LINQ: " + endTime2);
}

输出：

The running time of copy with iterative loop: 00:00:00.0005765                                                           
The running time of copy with LINQ: 00:00:02.5989753

为什么差异如此之大？我用其他类型做了这个实验：

Dictionary<int, float>, Dictionary<int, MyObject>-MyObject有 2 个成员，一个string和一个int。

在其他实验中，Linq 和 Non-Linq 之间存在差异，但只是Dictionary<int, int>时间差异如此之大。

标签： c#performancelinq

解决方案

不同之处之一是“迭代”方法将容量传递给Dictionary构造函数，从而避免了重新散列。尽管 LINQ 实现可以执行相同的优化（目前完整的框架实现不能）。

但是产生很大性能差异的主要区别是您的 LINQ 实现

var dictionary3 = originalDictionary.ToDictionary(i => i, i => i);

不生产Dictionary<int, int>，但是Dictionary<KeyValuePair<int, int>, KeyValuePair<int, int>>！

那是因为i键和元素选择器中的类型都是KeyValuePair<int, int>since Dictionary<int, int>is IEnumerable<KeyValuePair<int, int>>。And GetHashCode/Equals支配操作（Dictionary.Add）的方法对于KeyValuePairstruct 比对于 simple慢得多int（调用多个方法时不计算 struct 堆栈复制开销）。

应该是这样的：

var dictionary3 = originalDictionary.ToDictionary(e => e.Key, e => e.Value);

它仍然会慢一些，但不会显着。

更新：正如@2kay 在评论中正确提到的那样，当和 与您的测试中相等时， GetHashCodeforKeyValuePair<int, int>返回一个相同的值，这是哈希结构的最坏情况，例如并进行（检查重复）操作（二次) 时间复杂度，并真正解释了此特定测试中性能的巨大差异。KeyValueDictionaryAddO(N^2)

推荐阅读