Linq-to-objects的处理时间是x次迭代的两倍

Question

我有一个实体列表，其中包含大约137000条记录，我循环遍历这些记录，然后需要将其链接到附加参数的元组列表，其中包含大约150000条记录

为什么它花费的时间越长，迭代次数就越多？这是从秒表中找到的: 136770个符合条件的项目。

处理了10,000个项目EllapsedTime: 5473，即: 0.0912166666666667分钟。

处理了20,000个项目EllapsedTime: 15307，即: 0.255116666666667分钟。

处理了30,000个项目EllapsedTime: 30065也就是: 0.501083333333333分钟。

处理了50,000个项目EllapsedTime: 74507也就是: 1.24178333333333分钟。

处理了75,000个项目EllapsedTime: 157836，即: 2.6306分钟。

处理了100,000个项目EllapsedTime: 272495也就是: 4.54158333333333分钟。

EllapsedTime: 499663也就是: 8.32771666666667分钟。

有什么方法可以优化这一点吗？

 List<Entites> alMatched 
List<Tuple<int, double, int, int>> lsItems = new List<Tuple<int, double, int, int>>();
IEnumerable<Tuple<int, double, int, int>> enumThingy = lsItems;

 for (int z = 0; z <= alMatched.Count() - 1;z++ )
            {
               Entity a = alMatched[z];
               var newRepl = enumThingy.Where(d => d.First == a.ID).First();
               if (newRepl != null)
               {

               }

                switch (z)
                {
                    case 10000:
                        Debug.Print("10,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 20000:
                        Debug.Print("20,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 30000:
                        Debug.Print("30,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 50000:
                        Debug.Print("50,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 75000:
                        Debug.Print("75,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 100000:
                        Debug.Print("100,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                }

            }

问候

_Eric

Answer 1

好的。尝试使用字典而不是列表

    List<Tuple<int, double, int, int>> lsItems = new List<Tuple<int, double, int, int>>();

//should be 

var lsItems = new Dictionary<int, Tuple<int, double, int, int>>();

使用以下命令/reference项目：

LsItemsa.ID newRepl = var；

Answer 2

看看这段代码：

for (int z = 0; z <= alMatched.Count() - 1;z++ )
{
    Entity a = alMatched[z];
    var newRepl = enumThingy.Where(d => d.First == a.ID).First();

在这种情况下(我怀疑您的“真实”情况)，enumThingy和alMatched枚举的顺序是相同的。

因此，当您处于第一种情况时，对enumThingy.Where的调用将在第一次迭代时返回。在100种情况下，需要100次迭代才能匹配您的条件，然后退出。在case 10000上，它需要10000次迭代。

基本上，你走得越远，情况就越糟。您的算法是O(N^2)，但是LINQ是捷径，因为您使用的是相同的列表，并且排序可以帮助您快速地“捷径”出where。

Answer 3

你可以在这里使用不同的方法来获得速度增益。

一种方法是使用哈希表将项存储在enumThingy中，并通过您要查找的键来访问它们。

另一种选择是对枚举对象和alMatched对象进行排序，然后使用“滑动方法”查找所需的所有项。

目前您正在处理一个枚举，它必须检查所有项以找到您需要的项，因此在链中找到您的项(或完全丢失)将花费越来越多的时间。