c# - LINQ ToDictionary 方法和 Copy Dictionary Iterative Loop 之间的性能差异

Question

在尝试查看使用 ToDictionary 复制字典之间的差异时并使用迭代循环复制字典，我看到了非常大的性能差异。
在下面的代码中，我创建了 Dictionary<int, int>并用 LINQ 和 Non 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>。时差这么大。

Answer 1

差异之一是“迭代”方法将容量传递给 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>自 Dictionary<int, int>是IEnumerable<KeyValuePair<int, int>> .和 GetHashCode/Equals主导操作(Dictionary.Add)的方法对于KeyValuePair要慢得多结构比简单 int (不计算调用多个方法时的结构堆栈复制开销)。

应该是这样的:

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

它仍然会慢一点，但不会很明显。

更新:正如@2kay 在评论中正确提到的那样，GetHashCode对于 KeyValuePair<int, int>当 Key 时返回一个相同的值和 Value与您的测试相同，这是像 Dictionary 这样的哈希结构的最坏情况并制作Add (检查重复项)操作 O(N^2) (二次)时间复杂度，真正解释了此特定测试中性能的巨大差异。