C# Lambda 表达式速度

Question

我以前没有使用过很多 lambda 表达式，但我遇到过一种情况，我认为我可以巧妙地使用一个表达式。我有一个约 19,000 条记录的自定义列表，我需要查明列表中是否存在记录，因此我决定尝试以下操作，而不是编写一堆循环或使用 linq 来遍历列表：

for (int i = MinX; i <= MaxX; ++i)
{
    tempY = MinY;

    while (tempY <= MaxY)
    {
        bool exists = myList.Exists(item => item.XCoord == i && item.YCoord == tempY);

        ++tempY;
    }
}

唯一的问题是它执行大约需要 9 - 11 秒。我做错了什么吗？这只是我不应该使用这样的表达式的情况吗？

谢谢。

编辑：抱歉。我应该详细说明。我正在使用 for 和 while 循环创建一个记录列表，并检查该记录是否存在于 myList 中。这是我能想到的唯一方法。我会重新评估它，看看我能得到什么。

Answer 1

这段代码对我来说毫无意义，所以很难说你是否做错了。是的，你做错了的可能性很大。

与其显示代码，不如尝试这个。假设您有一个方法完全可以实现您想要的功能。该方法的签名是什么？不是正文，只是签名。

例如，假设您想问“这个点列表是否包含特定点？”那么签名将是

bool Contains(List<Point> list, Point p)

假设您想问问题“这个点列表是否包含此矩形内的任何点？”那么签名将是

bool ContainsAny(List<Point> list, Rectangle r)

假设您想问“这两个列表有哪些共同点？”那么签名就是

List<Point> Intersection(List<Point> l1, List<Point> l2)

等等。更清楚地说明您想要做什么，我们可以帮助您优化该操作。从签名开始。

Answer 2

这不是 lambda 的问题，而是你的算法的问题。你从 MinX 循环到 MaxX 是多少？然后您将循环从 MinY 到 MaxY，然后您将循环大约 19,000 条记录。因此，如果 X 循环为 10，y 循环为 10，那么您将进行 19,000*10*10 次调用。情况可能会更糟。

Answer 3

你的算法效率低下。如果您在同一个列表上进行多次搜索，则需要：

1. 排序适当地列表（通过您的查找键）。
2. 使用二分搜索查找正确的记录。

如果内存不是问题并且您希望速度非常快，您的另一个选择是将记录放入 Dictionary 中。设置完成后，这将为您提供最快的访问速度。

Answer 4

这不是你想要的吗？

myList.Where(
    item=>item.XCoord>=MinX
        &&item.XCoord<=MaxX
        &&item.YCoord>=MinY
        &&item.YCoord<=MaxY
)

所有生成的项目都将满足 exists 标准。

……还是我理解错了？

Answer 5

我将用一个很好的基于 linq 的解决方案来扩展 Kevin 的答案。

原始代码有效地计算了一个二维布尔数组，指示在 x 处的 myList 中是否存在坐标。每个数组元素的 y 坐标。

用于每个 x & 的测试y 可以表示为 lambda 函数，如下所示：

Func<int, int, bool> original =
    (x, y) =>
        myList.Exists(item => item.XCoord == x && item.YCoord == y);

这是低效的，因为调用 Exists 方法，因此对于每个 xx 都会迭代列表代码> & y 坐标已测试。是否迭代整个列表取决于是否找到匹配项。在很多情况下，不会有匹配项，因此整个列表会被多次访问。

因此，最好预先计算字典的字典，以确定 myList 中是否存在任何 x & 的坐标。 y 坐标。

var xyLookup =
    (from item in myList
     group item by item.XCoord into XCoords
     select new
     {
         X = XCoords.Key,
         YLookup = (from x in XCoords
                    group x by x.YCoord into YCoords
                    select new
                    {
                        Y = YCoords.Key,
                        Coords = YCoords
                    }).ToDictionary(a => a.Y, a => a.Coords)
     }).ToDictionary(b => b.X, b => b.YLookup);

xyLookup 现在允许以下 lambda 函数替换原始版本。

Func<int, int, bool> refactored =
    (x, y) =>
        xyLookup.ContainsKey(x) && xyLookup[x].ContainsKey(y);

预计算 xyLookup 需要一些时间，因此根据我的测试，如果我有一个 3x3 数组并且 myList 包含 3 个坐标，那么两种方法的速度大致相同。不过，我预计 myList 中的实际数组大小和元素数量在实践中会大得多。

如果我在 myList 中有一个包含 10,000 个坐标的 100x100 数组，则 xyLookup 比原始方法快大约 91 倍。

我喜欢 linq...:-)