为什么linq在c#中很慢

Question

我突然对 linq 性能和运行一些测试感到好奇。

下面是我的测试代码，结果非常令人惊讶。

谁能知道 linq 是如何工作的，为什么比 TryOut 慢？

Public class TestObject
{
 ....
 ....
 //this class contain many members 
 bool deleted;
 ....
}

class Program
{
    public static ConcurrentDictionary<string, TestObject> testDictionary = new ConcurrentDictionary<string, TestObject>();

static void Main(string[] args)
{
 //testDictionary is initialized in ohter code and is likely to have 10000 elements.
  RandomTest(0);
  RandomTest(1);
  Console.ReadKey();
}

static void RandomTest(int k)
{
    int count = 10000;
    List<string> randomId = new List<string>();
    Random rnd = new Random();
    for (int i = 0; i < count; i++)
    {
         int randomNumber = rnd.Next(0, testDictionary.Count());
         randomId.Add(testDictionary.ElementAt(randomNumber).key);
    }
    Stopwatch sw = new Stopwatch();
    sw.Start(); 

    if (k == 0)
    {

         for (int i = 0; i < count; i++)
         {
             var res = checkid(randomId[i]);
         }
    }
    else if (k == 1)
    {
         for (int i = 0; i < count; i++)
         {
             var res = checkid2(randomId[i]);
         }
    }
    sw.Stop();
    Console.WriteLine("Elapsed time : " + sw.Elapsed);
}
static bool checkid(string id)
{
    TestObject t;
    return !testDictionary.TryGetValue(id, out t) ?
          false : t.deleted ?
          false : true;
}
static bool checkid2(string id)
{
    return testDictionary.Any(t => t.key == id && !t.Value.deleted)? true : false;
}

我运行这两种方法10000次，结果如下

checkid方式，大部分用时不到00:00:00.002.

对于checkid2方法，大部分时间在00:00:02.2和00:00:02.4.

之间

这是一个巨大的差异。

这是因为checkid2方法即使key不等于Id也会检查删除的变量，而checkid方法只有在找到对应的key时才会检查删除的变量？

Answer 1

Dictionary.TryGetValue 使用散列来定位元素，因此它是一个 O(1) 操作。

Dictionary.Any 将遍历集合以尝试找到符合条件的集合。那是 O(n).

通常 - LINQ 会比使用 for/foreach 的 hand-crafting 循环慢一点，但在大多数情况下性能差异无关紧要。您在这里遇到的不是 LINQ 变慢，而是 Dictionary<T>.TryGetValue 变快，因为它的内部结构针对 key-based 搜索进行了优化。如果您将其更改为 List<T> 并编写 for 循环以线性方式执行相同的搜索（就像 LINQ 在幕后所做的那样），您会发现差异变得更小。

Answer 2

@MarcinJuraszek 回答正确。但我想添加一些相关的 LINQ 信息来完成答案。是的，散列与迭代行为的主要区别很明显，但是您需要了解更多关于 .NET 中的 LINQ

对于 checkid，IL 如下所示：

IL_0000: ldsfld class [mscorlib]System.Collections.Concurrent.ConcurrentDictionary`2<string, class ConsoleApp5.TestObject> ConsoleApp5.Program::testDictionary
IL_0005: ldarg.0
IL_0006: ldloca.s t
IL_0008: callvirt instance bool class [mscorlib]System.Collections.Concurrent.ConcurrentDictionary`2<string, class ConsoleApp5.TestObject>::TryGetValue(!0, !1&)
IL_000d: brfalse.s IL_001b

IL_000f: ldloc.0
IL_0010: ldfld bool ConsoleApp5.TestObject::deleted
IL_0015: brtrue.s IL_0019

IL_0017: ldc.i4.1
IL_0018: ret

IL_0019: ldc.i4.0
IL_001a: ret

IL_001b: ldc.i4.0
IL_001c: ret

它完全按照你的想法去做（你在代码中写的）。

但是 checkid2 这样做：

IL_0000: newobj instance void ConsoleApp5.Program/'<>c__DisplayClass4_0'::.ctor()
IL_0005: stloc.0
IL_0006: ldloc.0
IL_0007: ldarg.0
IL_0008: stfld string ConsoleApp5.Program/'<>c__DisplayClass4_0'::id
IL_000d: ldsfld class [mscorlib]System.Collections.Concurrent.ConcurrentDictionary`2<string, class ConsoleApp5.TestObject> ConsoleApp5.Program::testDictionary
IL_0012: ldloc.0
IL_0013: ldftn instance bool ConsoleApp5.Program/'<>c__DisplayClass4_0'::'<checkid2>b__0'(valuetype [mscorlib]System.Collections.Generic.KeyValuePair`2<string, class ConsoleApp5.TestObject>)
IL_0019: newobj instance void class [mscorlib]System.Func`2<valuetype [mscorlib]System.Collections.Generic.KeyValuePair`2<string, class ConsoleApp5.TestObject>, bool>::.ctor(object, native int)
IL_001e: call bool [System.Core]System.Linq.Enumerable::Any<valuetype [mscorlib]System.Collections.Generic.KeyValuePair`2<string, class ConsoleApp5.TestObject>>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!0>, class [mscorlib]System.Func`2<!!0, bool>)
IL_0023: brtrue.s IL_0027

IL_0025: ldc.i4.0
IL_0026: ret

IL_0027: ldc.i4.1
IL_0028: ret

并且 "real" 检查 ID 逻辑在这里（在 <>c__DisplayClass4_0.<checkid2>b__0 下）：

IL_0000: ldarga.s t
IL_0002: call instance !0 valuetype [mscorlib]System.Collections.Generic.KeyValuePair`2<string, class ConsoleApp5.TestObject>::get_Key()
IL_0007: ldarg.0
IL_0008: ldfld string ConsoleApp5.Program/'<>c__DisplayClass4_0'::id
IL_000d: call bool [mscorlib]System.String::op_Equality(string, string)
IL_0012: brfalse.s IL_0024

IL_0014: ldarga.s t
IL_0016: call instance !1 valuetype [mscorlib]System.Collections.Generic.KeyValuePair`2<string, class ConsoleApp5.TestObject>::get_Value()
IL_001b: ldfld bool ConsoleApp5.TestObject::deleted
IL_0020: ldc.i4.0
IL_0021: ceq
IL_0023: ret

IL_0024: ldc.i4.0
IL_0025: ret

此代码创建一个新的编译器生成类型 <>c__DisplayClass4.0，将 id 保存为 class 成员，创建对 <>c__DisplayClass4_0'::'<checkid2>b__0 的委托以获取 KeyValuePair 和 return bool 并调用 Any 以使用此委托。

除此之外，事实是 Any 是 O(n) 而 Dictionary 是 O(1) - 正如 Marcin 所写 - 你得到了答案。

为什么linq在c#中很慢

Why is linq slow in c#

.net

c#

linq

clr

performance