时间戳

首页 > 解决方案 > 如何有效地用另一个列表更新一个列表 C#

c# - 如何有效地用另一个列表更新一个列表 C#

问题描述

我有两个包含对象元素的列表，一个大列表我们称之为 List1，另一个小列表 List2。我需要根据函数中定义的条件用 List2 中的值更新 List1 中的值，该函数根据对象中的值返回布尔值。我提出了以下实现，对于较大的列表确实需要大量时间。

检查项目是否将被更新的功能

private static bool CheckMatch(Item item1, Item item2) { 
//do some stuff here and return a boolean
}

我用来更新项目的查询

在下面的片段中，我需要用 List2（小列表）中的一些值更新 List1（大列表）

    foreach(var item1 in List1)
    {
        var matchingItems = List2.Where(item2 => CheckMatch(item1, item2));
        if (matchingItems.Any())
        {
            item1.IsExclude = matchingItems.First().IsExcluded;
            item1.IsInclude = matchingItems.First().IsIncluded;
            item1.Category = matchingItems.First().Category;
        }
    }

我希望我能得到一个比这更好的解决方案。我还需要保持 List1 中元素的位置

这是我正在做 的样本 这是我正在做的样本

标签： c#listlinqbig-o

解决方案

正如 LP13 的回答所指出的那样，您通过重新执行查询而不是执行一次并缓存结果来进行大量的重新计算。

但这里更大的问题是，如果您在中有n项目List1和m潜在匹配项List2，并且您正在寻找任何匹配项，那么最坏的情况下您肯定会进行n * m匹配。如果n和m很大，则它们的乘积会更大。由于我们正在寻找任何匹配，最坏的情况是没有匹配；你一定会尝试所有的m可能性。

这个成本可以避免吗？也许吧，但前提是我们知道一些可以利用的技巧，并且您已经使问题变得如此抽象——我们有两个列表和一个关系，没有关于列表或关系的信息——没有结构我们可以利用。

也就是说：如果您碰巧知道其中有一个元素List2可能与其中的许多项目匹配，List1则将该元素放在首位。 Any, 或, 将在获得第一个匹配项后FirstOrDefault停止执行查询，因此您可以将问题转化为问题。WhereO(n * m)O(n)

如果不了解更多的关系是什么，很难说如何提高性能。

更新：一位评论者指出，如果我们知道该关系是等价关系，我们可以做得更好。是等价关系吗？也就是说，假设我们有您的方法来检查两个项目。我们能保证以下吗？

  • 这种关系是自反的：CheckMatch(a, a)总是正确的。
  • 关系是对称的：CheckMatch(a, b)总是与CheckMatch(b, a)
  • 该关系是传递的：如果CheckMatch(a, b)为真并且CheckMatch(b, c)为真，则CheckMatch(a, c)始终为真

如果我们具备这三个条件，那么您可以做得更好。这种关系将元素划分为等价类。您所做的是将每个项目与List1规范值相关联。该规范值对于等价类的每个成员都是相同的。然后，您可以从该字典中进行快速查找并快速解决您的问题。List2

但是，如果您的关系不是等价关系，则此方法行不通。

推荐阅读